Сакурако та Різдвяний масив

Сакурако нещодавно прикрасила масив так, що він став Різдвяним масивом. Він був святковим, поки Чефір не прийшов і не зіпсував його.

Масив довжини $n$ називається святковим, якщо виконується наступне:

• для кожного $i$ $(1\le i\le n)$ $a_i=a_{n-i+1}$;

• і є елемент, який зустрічається строго більше ніж $\frac{n}{2}$ разів.

Вам дано масив $a$ довжини $n$, де $n$ парне. Вам потрібно визначити мінімальну кількість елементів, які потрібно замінити, щоб цей масив став святковим.

«Замінити» означає вибрати будь-яке $i$ $(1\le i\le n)$ та присвоїти $a_i=x$, де $x$ — будь-яке ціле число (навіть якщо число $x$ не зустрічалось в масиві).

Вхідні дані

Перший рядок містить одне ціле число $n$ ($2\le n\le 5\cdot 10^5$; $n$ парне), яке позначає довжину масиву.

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

Вихідні дані

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

Приклади

Примітка

Оптимальний набір замін в 1 прикладі:

$[2,6,4,6,2,9]\to [2,2,6,6,2,2]$ Для цього масиву обидві умови виконуються:

• для кожного $i(1\le i\le n)$ $a_i=a_{n-i+1}$

• ціле число $2$ зустрічається більше ніж $\frac{6}{2}=3$ рази в нашому масиві.

Ми можемо показати, що це мінімальна кількість операцій, які потрібно виконати.

В прикладі 2 оптимальна заміна:

$[3,7,2,4,9,3]\to [3,4,4,4,4,3]$

Можна показати, що це найменша кількість операцій, які потрібно виконати.

Оцінювання

Ви отримаєте принаймні $10$ балів, якщо ваше рішення працює правильно для $a_i=a_{i+1}$ для кожного $(1\le i<n)$.

Ви отримаєте принаймні $20$ балів, якщо ваше рішення працює правильно для $a_i=a_{n-i+1}$ для кожного $i$ $(1\le i\le n)$.

Ви отримаєте принаймні $30$ балів, якщо ваше рішення працює правильно для $n\le 1000$.

Ви отримаєте додаткові $40$ балів, якщо ваше рішення працює правильно без будь-яких обмежень.