Вам задана последовательность целых чисел \(a_1, a_2, \dots, a_n\).
Вы можете применять следующую операцию к этой последовательности: выбрать число \(x\) и переместить все элементы равные \(x\) либо в начало, либо в конец массива \(a\). Обратите внимание, что за одну операцию вы перемещаете все элементы в одном направлении.
Например, если \(a = [2, 1, 3, 1, 1, 3, 2]\), вы можете получить следующие последовательности за одну операцию (для удобства, обозначим элементы равные \(x\) как \(x\)-элементы):
- \([1, 1, 1, 2, 3, 3, 2]\), если вы переместите все \(1\)-элементы в начало;
- \([2, 3, 3, 2, 1, 1, 1]\), если вы переместите все \(1\)-элементы в конец;
- \([2, 2, 1, 3, 1, 1, 3]\), если вы переместите все \(2\)-элементы в начало;
- \([1, 3, 1, 1, 3, 2, 2]\), если вы переместите все \(2\)-элементы в конец;
- \([3, 3, 2, 1, 1, 1, 2]\), если вы переместите все \(3\)-элементы в начало;
- \([2, 1, 1, 1, 2, 3, 3]\), если вы переместите все \(3\)-элементы в конец;
Вам нужно посчитать минимальное количество операций, после применения которых последовательность \(a\) станет отсортирована в порядке неубывания. Последовательность отсортирована в порядке неубывания, если для любого индекса \(i\) от \(2\) до \(n\), выполняется условие \(a_{i-1} \le a_i\).
Обратите внимание, что вам нужно ответить на \(q\) независимых запросов.
Примечание
В первом запросе вы можете переместить все \(1\)-элементы в начало (после этого последовательность превратится в \([1, 1, 1, 3, 6, 6, 3]\)) и затем переместить все \(6\)-элементы в конец.
Во втором запросе последовательность отсортирована изначально, а значит ответ равен нулю.
В третьем запросе вам нужно переместить все \(2\)-элементы в начало.