Багато людей вважають, що улюблене число Козака Вуса — це сім. Проте, вони помиляються. Насправді його улюблене число — це два. Саме тому він полюбляє лише ті масиви, у яких рівно два різні числа.
Попри це, звичайні масиви з лише двома різними числами йому здаються досить хаотичними, а Козак ненавидить хаос. Саме тому, що любить ті масиви, де кожні два сусідні елементи різні.
Формально, щоб масив сподобався Вусу, потрібно, щоб виконувалися наступні умови:
ai=ai+2 для всіх i (1≤i≤n−2);
ai=ai+1 для всіх i (1≤i≤n−1).
Наприклад, йому подобається масив [1,4,1,4,1]. У цьому масиві лише два різні числа 1 та 4. А також немає двох сусідніх чисел з однаковим значенням. Проте йому не подобаються масиви [1,4,5] (бо тут три різні числа), [1,1,1,1,1] (бо тут однакові сусідні елементи, а також лише одне число), [7,7,6,6] (бо тут однакові сусідні елементи).
Дано масив a з n цілих чисел a1,a2,…,an. Потрібно змінити мінімальну кількість чисел, щоб цей масив сподобався Козаку Вусу. Знайдіть цю мінімальну кількість.
Наприклад, у масиві [1,1,1,1,1] потрібно змінити другий та четвертий елементи на будь-яке інше число. Тому у цьому прикладі відповідь буде 2.
Перший рядок містить одне ціле число n (1≤n≤105) — кількість чисел у масиві.
Другий рядок містить n цілих чисел a1,a2,…,an (1≤ai≤109) — числа масиву.
Виведіть мінімальну кількість чисел, які потрібно змінити, щоб масив сподобався Козаку.
Рішення, які працюватимуть правильно при обмеженнях n≤100 та ai≤100, отримуватимуть 40 балів.