Даже в университете студентам нужно отдыхать. Именно поэтому учитель Сакурако решил организовать экскурсию. Известно, что все студенты будут идти в одну линию.
Студент с индексом \(i\) имеет некоторую тему интереса, которая описывается как \(a_i\). Как учитель, вы хотите минимизировать отвлечение в линии студентов.
Отвлечение линии определяется как количество соседей с одинаковой темой интереса. Другими словами, отвлечение — это количество индексов \(j\) (\(1 \le j < n\)), таких что \(a_j = a_{j + 1}\).
Чтобы сделать это, вы можете выбрать индекс \(i\) (\(1\le i\le n\)) и поменять местами студентов на позициях \(i\) и \(n-i+1\). Вы можете выполнять любое количество обменов.
Ваша задача — определить минимальное отвлечение, которое вы можете достичь, выполняя описанную выше операцию любое количество раз.
Выходные данные
Для каждого набора входных данных выведите минимально возможное отвлечение линии, которое вы можете достичь.
Примечание
В первом примере нужно применить операцию к \(i=2\), таким образом массив станет равен \([1, \textbf{2}, 1, \textbf{1}, 3]\), жирным выделены элементы, которые поменялись местами. Отвлечение этого массива равна \(1\).
В четвёртом примере достаточно применить операцию к \(i=3\), таким образом массив станет равен \([2, 1, \textbf{2}, \textbf{1}, 2, 4]\). Отвлечение этого массива равна \(0\).
В восьмом примере достаточно применить операцию к \(i=3\), таким образом массив станет равен \([1, 4, \textbf{1}, 5, \textbf{3}, 1, 3]\). Отвлечение этого массива равна \(0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9
5
1 1 1 2 3
6
2 1 2 2 1 1
4
1 2 1 1
6
2 1 1 2 2 4
4
2 1 2 3
6
1 2 2 1 2 1
5
4 5 5 1 5
7
1 4 3 5 1 1 3
7
3 1 3 2 2 3 3
|
1
2
1
0
0
1
1
0
2
|