F. Борющийся участник
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Чтобы помочь тем участникам, которые испытывают трудности в большинстве контестов, основатели Codeforces решили ввести Дивизион 5. В этом новом дивизионе теги всех задач будут анонсированы перед началом раунда, чтобы помочь его участникам.

Контест состоит из $$$n$$$ задач, где тег $$$i$$$-й задачи определяется целым числом $$$a_i$$$.

Вы хотите совершить AK (All Kill, решить все задачи). Чтобы это сделать, вы должны решить все задачи в некотором порядке. Чтобы было веселее писать контест, вы задали себе дополнительные ограничения. Вы не хотите подряд решать две задачи с одинаковым тегом, потому что это скучно. Также, вы боитесь больших прыжков в сложности во время решения задач, поэтому вы хотите минимизировать количество раз, когда вы подряд решаете две задачи, не соседние в порядке задач контеста.

Более формально, ваш порядок решения задач может быть задан перестановкой $$$p$$$ длины $$$n$$$. Цена перестановки определяется как количество индексов $$$i$$$ ($$$1\le i<n$$$), таких что $$$|p_{i+1}-p_i|>1$$$. У вас есть требование, что $$$a_{p_i}\ne a_{p_{i+1}}$$$ для всех $$$1\le i< n$$$.

Вы хотите найти минимальную возможную цену перестановки, которая удовлетворяет этому требованию. Если не существует перестановок, которые ему удовлетворяют, сообщите об этом.

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

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

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

В следующей строке находится $$$n$$$ целых чисел $$$a_1,a_2,\ldots a_n$$$ ($$$1 \le a_i \le n$$$) — теги задач.

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

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

Для каждого набора входных данных, если не существует перестановок, удовлетворяющих необходимому требованию, выведите $$$-1$$$. Иначе выведите минимальную возможную цену переставновки, удовлетворяющей требованию.

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

В первом наборе входных данных рассмотрим $$$p=[5, 4, 3, 2, 1, 6]$$$. Цена этой перестановки будет $$$1$$$, потому что мы прыгаем с $$$p_5=1$$$ на $$$p_6=6$$$ и $$$|6-1|>1$$$. Эта перестановка удовлетворяет требованию, потому что мы не решаем подряд две задачи с одинаковым тегом. Невозможно получить цену, меньшую чем $$$1$$$.

Во втором наборе входных данных рассмотрим $$$p=[1,5,2,4,3]$$$. Цена этой перестановки будет $$$3$$$, потому что $$$|p_2-p_1|>1$$$, $$$|p_3-p_2|>1$$$ и $$$|p_4-p_3|>1$$$. Эта перестановка удовлетворяет требованию, потому что мы не решаем подряд две задачи с одинаковым тегом. Невозможно получить цену, меньшую чем $$$3$$$.

В третьем наборе входных данных для любого порядка решения задач мы будем подряд решать хотя бы одну пару задач с одинаковым тегом, поэтому ответ $$$-1$$$.