C. Изменение последовательности
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задана последовательность $$$a$$$, изначально состоящая из $$$n$$$ целых чисел.

Вы хотите изменить эту последовательность таким образом, чтобы все элементы в ней были равны между собой (то есть чтобы она состояла из какого-то количества вхождений одного элемента).

Чтобы это сделать, вы выбираете какое-то целое число $$$x$$$, которое встречается в $$$a$$$ хотя бы раз, и затем совершаете следующую операцию любое количество раз (возможно, нулевое): выбираете какой-то отрезок последовательности $$$[l, r]$$$ и удаляете его. Но есть одно исключение: вы не можете выбирать отрезки, которые содержат $$$x$$$. Более формально, вы выбираете какую-то такую последовательную подпоследовательность $$$[a_l, a_{l + 1}, \dots, a_r]$$$, что $$$a_i \ne x$$$ для $$$l \le i \le r$$$, и удаляете ее. После удаления индексация элементов справа от удаленного отрезка меняется: элемент, который был $$$(r+1)$$$-м, становится $$$l$$$-м, элемент, который был $$$(r+2)$$$-м, становится $$$(l+1)$$$-м, и так далее (то есть последовательность просто схлопывается).

Заметьте, что вы не можете изменять $$$x$$$ после того, выбрали его.

Например, пусть $$$n = 6$$$, $$$a = [1, 3, 2, 4, 1, 2]$$$. Тогда одним из способов изменить ее за две операции является выбрать $$$x = 1$$$, а затем:

  1. выбрать $$$l = 2$$$, $$$r = 4$$$, после чего получится последовательность $$$a = [1, 1, 2]$$$;
  2. выбрать $$$l = 3$$$, $$$r = 3$$$, после чего получится последовательность $$$a = [1, 1]$$$.

Заметьте, что выбор $$$x$$$ не является операцией. Также заметьте, что вы не можете удалять никакое вхождение $$$x$$$.

Ваша задача — найти минимальное количество операций, необходимое для того, чтобы изменить последовательность так, как описано выше.

Вам необходимо ответить на $$$t$$$ независимых наборов тестовых данных.

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

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — количество наборов тестовых данных. Затем следуют $$$t$$$ наборов тестовых данных.

Первая строка набора тестовых данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество элементов в $$$a$$$. Вторая строка набора тестовых данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$), где $$$a_i$$$ равно $$$i$$$-му элементу $$$a$$$.

Гарантируется, что сумма $$$n$$$ не превосходит $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$).

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

Выведите ответ на каждый набор тестовых данных — минимальное количество операций, необходимое для того, чтобы изменить заданную последовательность так, как описано в условии задачи. Можно доказать, что всегда возможно совершить конечную последовательность операций таким образом, чтобы последовательность изменилась необходимым образом.

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