Sakurako nemrégiben egy tömböt díszített fel úgy, hogy az Karácsonyi tömbbé vált. Ez fényes volt, amíg Chefir meg nem zavarta.
Egy hosszúságú tömb fényes-nek nevezhető, ha a következő érvényes:
minden esetén (1\le i\le n) a_i=a_{n-i+1};
és van egy elem, amely legalább \frac{n}{2} alkalommal előfordul.
Adott egy tömb, amelynek hossza , ahol páros. Meg kell határoznod, hogy hány elemet kell minimálisan kicserélni ahhoz, hogy ez a tömb fényes legyen.
A "kicserél" azt jelenti, hogy választhatsz bármely -t (1\le i\le n), és hozzárendelheted a_i=x-et, ahol egy tetszőleges egész szám (akkor is, ha nem létezik a tömbben).
Az első sorban egy egész szám (2\le n \le 5 \cdot 10^5; páros), amely a tömb hosszát jelöli.
A második sorban egész szám található: a_1, a_2, \dots, a_n (1\le a_i\le 10^6).
Egy sorban adj meg egy egész számot, amely a minimális elemek számát jelöli, amelyeket ki kell cserélni ahhoz, hogy fényes tömbbé váljon.
1. példa
2. példa
Optimális csere az 1. tesztesetben:
[2,6,4,6,2,9]\to [2,\textcolor{red}{2,6},6,2,\textcolor{red}{2}] Ezen tömb esetén mindkét feltétel teljesül:
minden i\, (1\le i\le n) esetén a_i=a_{n-i+1}
a egész szám több mint \frac{6}{2}=3 alkalommal előfordul a tömbünkben.
Meg tudjuk mutatni, hogy ez a minimális műveletek száma, amit végre kell hajtanunk.
A 2. tesztesetben az optimális csere:
[3,7,2,4,9,3]\to [3,\textcolor{red}{4,4},4,\textcolor{red}{4},3]
Meg lehet mutatni, hogy ez a legkisebb műveletek száma, amit végre kell hajtanunk.
Legalább pontot kapsz, ha a megoldásod helyesen működik, ha a_i=a_{i+1} minden (1\le i<n) esetén.
Legalább pontot kapsz, ha a megoldásod helyesen működik, ha a_i=a_{n-i+1} minden esetén (1\le i\le n).
Legalább pontot kapsz, ha a megoldásod helyesen működik, ha n\le 1000.
További pontot kapsz, ha a megoldásod helyesen működik korlátozások nélkül.