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

Багато людей вважають, що улюблене число Козака Вуса — це сім. Проте, вони помиляються. Насправді його улюблене число — це два. Саме тому він полюбляє лише ті масиви, у яких рівно два різні числа.

Попри це, звичайні масиви з лише двома різними числами йому здаються досить хаотичними, а Козак ненавидить хаос. Саме тому, що любить ті масиви, де кожні два сусідні елементи різні.

Формально, щоб масив сподобався Вусу, потрібно, щоб виконувалися наступні умови:

• $a_i=a_{i+2}$ для всіх $i$ ($1\le i\le n-2$);

• $a_i\ne a_{i+1}$ для всіх $i$ ($1\le i\le n-1$).

Наприклад, йому подобається масив $[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$.

Input

Перший рядок містить одне ціле число $n$ ($1\le n\le 10^5$) — кількість чисел у масиві.

Другий рядок містить $n$ цілих чисел $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^9$) — числа масиву.

Output

Виведіть мінімальну кількість чисел, які потрібно змінити, щоб масив сподобався Козаку.

Examples

Scoring

Рішення, які працюватимуть правильно при обмеженнях $n\le 100$ та $a_i\le 100$, отримуватимуть $40$ балів.