Sakurako és egy Karácsonyi Tömb#351

Sakurako és egy Karácsonyi Tömb

1,5 másodperc
256 megabájt
Nehéz

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:

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).

Bemenet

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).

Kimenet

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.

Példák

1. példa

Loading
Loading

2. példa

Loading
Loading

Megjegyzés

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.

Pontozás

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.