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

У вас есть массив $$$a$$$ из $$$n$$$ целых чисел.

Вы можете не более одного раза применить следующую операцию: выбрать три целых числа $$$i$$$, $$$j$$$, $$$x$$$ ($$$1 \le i \le j \le n$$$) и присвоить всем элементам массива с индексами от $$$i$$$ до $$$j$$$ значение $$$x$$$. Цена данной операции зависит от выбранных индексов и равна $$$(j - i + 1)$$$ бурлей.

Например, массив равен $$$[1, 2, 3, 4, 5, 1]$$$. Если мы выберем $$$i = 2, j = 4, x = 8$$$, то после применения данной операции массив будет равен $$$[1, 8, 8, 8, 5, 1]$$$.

Какое наименьшее количество бурлей нужно потратить, чтобы сделать все элементы массива равными?

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

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

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

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

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

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

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

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