D. Сортировка последовательности
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задана последовательность целых чисел $$$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$$$ независимых запросов.

Входные данные

Первая строка содержит целое число $$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$) — количество запросов. Каждый запрос состоит из двух последовательных строк.

Первая строка каждого запроса содержит целое число $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — количество элементов массива.

Вторая строка каждого запроса содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots , a_n$$$ ($$$1 \le a_i \le n$$$) — элементы массива.

Гарантируется, что сумма $$$n$$$ по всем запросам не превосходит $$$3 \cdot 10^5$$$.

Выходные данные

На каждый запрос выведите одно число — минимальное количество операций для сортировки последовательности $$$a$$$ в порядке неубывания.

Пример
Входные данные
3
7
3 1 6 6 3 1 1
8
1 1 4 4 4 7 8 8
7
4 2 5 2 6 2 7
Выходные данные
2
0
1
Примечание

В первом запросе вы можете переместить все $$$1$$$-элементы в начало (после этого последовательность превратится в $$$[1, 1, 1, 3, 6, 6, 3]$$$) и затем переместить все $$$6$$$-элементы в конец.

Во втором запросе последовательность отсортирована изначально, а значит ответ равен нулю.

В третьем запросе вам нужно переместить все $$$2$$$-элементы в начало.