Чтобы помочь тем участникам, которые испытывают трудности в большинстве контестов, основатели 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\).
Вы хотите найти минимальную возможную цену перестановки, которая удовлетворяет этому требованию. Если не существует перестановок, которые ему удовлетворяют, сообщите об этом.
Выходные данные
Для каждого набора входных данных, если не существует перестановок, удовлетворяющих необходимому требованию, выведите \(-1\). Иначе выведите минимальную возможную цену переставновки, удовлетворяющей требованию.
Примечание
В первом наборе входных данных рассмотрим \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|