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

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

1,5 секунди
256 мегабайтів
Складна

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

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

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

«Замінити» означає вибрати будь-яке (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

Loading
Loading

Приклад 2

Loading
Loading

Примітка

Оптимальний набір замін в 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.

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