Вам дан массив \(a\) длины \(n\). Определим равность массива как количество индексов \(1 \le i \le n - 1\) таких, что \(a_i = a_{i + 1}\). Мы можем выполнять следующую операцию:
- Выберите любые два целых числа \(i\) и \(x\) такие, что \(1 \le i \le n - 1\) и \(1 \le x \le 10^9\). После этого, сделайте \(a_i\) и \(a_{i + 1}\) равными \(x\).
Найдите минимальное количество операций, необходимых для того, чтобы равность массива стала меньше или равна \(1\).
Выходные данные
Для каждого набора входных данных выведите минимальное количество необходимых операций.
Примечание
В первом наборе входных данных мы можем выбрать \(i=2\) и \(x=2\), получив \([1, 2, 2, 1, 1]\). Затем мы можем выбрать \(i=3\) и \(x=3\), получив \([1, 2, 3, 3, 1]\).
Во втором наборе входных данных мы можем выбрать \(i=3\) и \(x=100\), получив \([2, 1, 100, 100, 2]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
5
1 1 1 1 1
5
2 1 1 1 2
6
1 1 2 3 3 4
6
1 2 1 4 5 4
|
2
1
2
0
|