Editorial

Почнемо з того, що нам завжди вигідно змінювати числа лише на ті, які присутні в масиві.

Також розіб'ємо числа масиву на пари: $(a_i,a_{n+1-i})$ $(1\le i\le \frac{n}{2})$.

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

Для того, щоб знайти відповідь для фіксованого числа $x$, звернемо увагу на те, що кожна пара чисел може бути віднесена до однієї з 4 категорій:

1. $(x,x)$ (обидва числа з пари рівні $x$)

2. $(x,a)$ або $(a,x)$ (рівно одне число з пари рівне $x$)

3. $(a,a)$ (числа в парі одинакові, але не рівні $x$)

4. $(a,b)$ (числа в парі різні й не рівні числу $x$)

Кожну пару першого типу нам не вигідно змінювати взагалі.

Для досягнення умови $a_i=a_{n+1-i}$ $(1\le i\le \frac{n}{2})$, в масиві повинні залишитись лише пари типу $(x,x)$ та $(a,a)$.

Кожну пару 2 типу вигідно змінити на пару $(x,x)$.

Кожну пару 4 типу потрібно замінити або на пару типу $(a,a)$ або $(x,x)$. Якщо після замін пар другого типу на перший всього $x$ входить в масив $k$ разів (де $k\le \frac{n}{2}$), то нам потрібно ще перетворити пари 4 типу на пари першого типу, якщо навіть після перетворення всіх пар четвертого типу, кількість входжень числа $x$ недостатня, то ми змінюємо пари третього типу на пари першого типу.

Всі перевірки мінімальної кількості змін для фіксованого $x$ можна реалізувати за $O(1)$, перевірка всіх $x$ займе $O(n)$ часу.

Сумарний час роботи рішення $O(n)$.