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

Назовём массив $$$a$$$ красивым, если его можно превратить в массив из одинаковых чисел следующими операциями:

  • выбрать позицию $$$i$$$ ($$$2 \le i \le |a| - 1$$$) такую, что $$$a_{i - 1} = a_{i + 1}$$$, и заменить $$$a_i$$$ на $$$a_{i - 1}$$$.

Задан красивый массив $$$a_1, a_2, \dots, a_n$$$. Какое минимальное количество элементов надо из него удалить, чтобы он перестал быть красивым? Переставлять элементы местами запрещается. Если это сделать невозможно, то выведите -1.

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

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

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

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

Дополнительные ограничения на входные данные:

  • в каждом наборе входных данных массив $$$a$$$ — красивый;
  • сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$.
Выходные данные

На каждый набор входных данных выведите одно целое число — минимальное количество элементов, которое надо удалить из массива $$$a$$$, чтобы он стал некрасивым. Если это сделать невозможно, то выведите -1.

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

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

Во втором наборе входных данных можно удалить число на позиции $$$5$$$, например.

Полученный массив будет $$$[1, 2, 1, 2]$$$. Проверим, красивый ли он. Доступны две операции:

  • Выбрать $$$i = 2$$$: получится массив $$$[1, 1, 1, 2]$$$. К нему больше не применишь операций, а числа не все одинаковые.
  • Выбрать $$$i = 3$$$: получится массив $$$[1, 2, 2, 2]$$$. К нему тоже больше не применишь операций, и числа все еще не все одинаковые.

Получается, что массив $$$[1, 2, 1, 2]$$$ не является красивым.

В четвертом наборе входных данных можно удалить первые три элемента, например. Полученный массив $$$[5, 3, 3, 3]$$$ не является красивым.