e-olymp
Competitions

Ukrainian Olympiad in Informatics, III Stage, I Round

Прекрасний масив

Багато людей вважають, що улюблене число Козака Вуса~--- це сім. Проте, вони помиляються. Насправді його улюблене число~--- це два. Саме тому він полюбляє лише ті масиви, у яких рівно два різні числа. Попри це, звичайні масиви з лише двома різними числами йому здаються досить хаотичними, а Козак ненавидить хаос. Саме тому, що любить ті масиви, де кожні два сусідні елементи різні. Формально, щоб масив сподобався Вусу, потрібно, щоб виконувалися наступні умови: \begin{itemize} \item $a_i=a_{i+2}$ для всіх $i$ ($1 \leq i \leq n - 2$); \item $a_i\neq a_{i+1}$ для всіх $i$ ($1 \leq i \leq n - 1$). \end{itemize} Наприклад, йому подобається масив $[1, 4, 1, 4, 1]$. У цьому масиві лише два різні числа $1$ та $4$. А також немає двох сусідніх чисел з однаковим значенням. Проте йому не подобаються масиви $[1, 4, 5]$ (бо тут три різні числа), $[1, 1, 1, 1, 1]$ (бо тут однакові сусідні елементи, а також лише одне число), $[7, 7, 6, 6]$ (бо тут однакові сусідні елементи). Дано масив $a$ з $n$ цілих чисел $a_1, a_2, \dots, a_n$. Потрібно змінити мінімальну кількість чисел, щоб цей масив сподобався Козаку Вусу. Знайдіть цю мінімальну кількість. Наприклад, у масиві $[1, 1, 1, 1, 1]$ потрібно змінити другий та четвертий елементи на будь-яке інше число. Тому у цьому прикладі відповідь буде $2$. \InputFile Перший рядок містить одне ціле число $n$ ($1 \leq n \leq 10^5$)~--- кількість чисел у масиві. Другий рядок містить $n$ цілих чисел $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq 10^9$)~--- числа масиву. \OutputFile Виведіть мінімальну кількість чисел, які потрібно змінити, щоб масив сподобався Козаку. \Scoring Рішення, які працюватимуть правильно при обмеженнях $n \leq 100$ та $a_i \leq 100$, отримуватимуть $40$ балів.
Time limit 1 second
Memory limit 256 MiB
Input example #1
6
1 4 5 4 1 5
Output example #1
2
Input example #2
8
1 2 1 2 1 2 1 2
Output example #2
0
Input example #3
5
1 1 1 1 1
Output example #3
2
Author Anton Tsypko