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