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.be | szul.ki |
| 6 3 4 5 1 2 6 | 2 |