NézetNyomtat

Születésnap (Megoldás)
Versenyek > IOI > 2005 > 2. nap
Címkék > Feladat

Születésnap

Bájtember születésnapján $n$ gyerek vesz részt. Egy kerek asztal köré ülnek le, érkezési sorrendben az $1,2,\ldots,n$ helyekre, az óramutató járása szerinti körüljárási sorrendben.
Bájtember szülei tudják, hogy a gyerekek nagyon hangosak tudnak lenni, ha bizonyos párok túl közel ülnek egymáshoz, ezért ültetést rendeznek. Az általuk javasolt sorrend: $a_1,a_2, \ldots, a_n$, ahol $a_i$ szomszédai $a_{i-1}$ és $a_{i+1}$. (Mindkét körüljárás lehetséges!)
Az ültetés úgy történik, hogy minden gyerek feláll, és jobbra vagy balra néhány székkel arréb megy, ahol majd leül. Az ültetéskor keletkező káosz mértéke egyenlő a legnagyobb távolsággal, amit valamelyik gyerek megtett az asztal körül. A szülők ezt a káoszt szeretnék minimalizálni. Segítsünk nekik!

Feladat

Készíts programot, amely a gyerekek száma és a megkívánt permutáció alapján megadja, hogy mennyi a minimális káosz, amely árán a kívánt ülésrend elérhető.

Bemenet

Az input (szul.be) első sora a gyerekek $n$ számát, a következő sor pedig az $a_1,a_2, \ldots, a_n$ permutációt tartalmazza. ($1\le n\le 1000000$)

Kimenet

A kimenetnek (szul.ki) egyetlen számot, az ültetéshez szükséges minimális káosz mértékét kell tartalmaznia.

Példa

szul.beszul.ki
6 3 4 5 1 2 6 2

Tesztadatok

szul_teszt.zip
xxx.zip (Nagy tesztfájl.)