Сакурако нещодавно прикрасила масив так, що він став Різдвяним масивом. Він був святковим, поки Чефір не прийшов і не зіпсував його.
Масив довжини називається святковим, якщо виконується наступне:
для кожного (1\le i\le n) a_i=a_{n-i+1};
і є елемент, який зустрічається строго більше ніж \frac{n}{2} разів.
Вам дано масив довжини , де парне. Вам потрібно визначити мінімальну кількість елементів, які потрібно замінити, щоб цей масив став святковим.
«Замінити» означає вибрати будь-яке (1\le i\le n) та присвоїти a_i=x, де — будь-яке ціле число (навіть якщо число не зустрічалось в масиві).
Перший рядок містить одне ціле число (2\le n \le 5 \cdot 10^5; парне), яке позначає довжину масиву.
Другий рядок містить цілих чисел a_1, a_2, \dots, a_n (1\le a_i\le 10^6).
Виведіть в одному рядку одне ціле число, яке позначає мінімальну кількість елементів, які потрібно замінити, щоб став святковим масивом.
Приклад 1
Приклад 2
Оптимальний набір замін в 1 прикладі:
[2,6,4,6,2,9]\to [2,\textcolor{red}{2,6},6,2,\textcolor{red}{2}] Для цього масиву обидві умови виконуються:
для кожного i\, (1\le i\le n) a_i=a_{n-i+1}
ціле число зустрічається більше ніж \frac{6}{2}=3 рази в нашому масиві.
Ми можемо показати, що це мінімальна кількість операцій, які потрібно виконати.
В прикладі 2 оптимальна заміна:
[3,7,2,4,9,3]\to [3,\textcolor{red}{4,4},4,\textcolor{red}{4},3]
Можна показати, що це найменша кількість операцій, які потрібно виконати.
Ви отримаєте принаймні балів, якщо ваше рішення працює правильно для a_i=a_{i+1} для кожного (1\le i<n).
Ви отримаєте принаймні балів, якщо ваше рішення працює правильно для a_i=a_{n-i+1} для кожного (1\le i\le n).
Ви отримаєте принаймні балів, якщо ваше рішення працює правильно для n\le 1000.
Ви отримаєте додаткові балів, якщо ваше рішення працює правильно без будь-яких обмежень.