ŠIOM — Gimimo diena

Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: birthday.in

Rezultatų failas: birthday.out

Language:
Source file:
Jei norite pateikti savo sprendimą - prisijunkite.

Gimimo diena

Šiandien Baitmeno gimtadienis. Jame dalyvauja n vaikų (įskaitant Baitmeną). Vaikai sunumeruoti nuo 1 iki n. Baitmeno tėvai paruošė didelį apvalų stalą ir aplink jį sustatė n kėdžių. Atvykę vaikai susėda aplink stalą. Vaikas, kurio numeris 1, atsisės ant vienos iš kėdžių. Tada vaikas, kurio numeris 2, užims kėdę, esančią kairiau pirmojo vaiko. Vaikas, kurio numeris 3, atsisės ant tolesnės kėdės kairėje ir t. t. Galiausiai vaikas, kurio numeris n, atsisės ant paskutinės laisvos kėdės, kuri bus likusi tarp vaikų su numeriais 1 ir $n-1$ .

Baitmeno tėvai gerai pažįsta vaikus ir žino, kad kai kurie vaikas pešasi, jeigu sėdi arti. Tėvai ketina juos persodinti. Persodinimo tvarka nusakoma perstatymu (permutacija) $p_1$ , $p_2$ , ..., $p_n$ ( $p_1$ , $p_2$ , ..., $p_n$ yra skirtingi natūralieji skaičiai nuo 1 iki n) — vaikas, kurio numeris $p_1$ , turi sėdėti tarp vaikų su numeriais $p_n$ ir $p_2$ , vaikas, kurio numeris $p_i$ ( $i=2,3,\\dots,n-1$ ), turi sėdėti tarp vaikų su numeriais $p_{i-1}$ ir $p_{i+1}$ , o vaikas, kurio numeris $p_n$ , turi sėdėti tarp vaikų su numeriais $p_{n-1}$ ir $p_1$ . Atkreipkite dėmesį, kad vaikas su numeriu $p_1$ gali sėdėti vaiko $p_n$ kairėje arba dešinėje.

Norėdami susodinti vaikus reikiama tvarka, tėvai turi paprašyti vaikų atsikelti ir pereiti per tam tikrą skaičių kėdžių aplink stalą į kairę arba į dešinę. Jie turi nuspręsti, kur kiekvienas vaikas turi eiti — tai yra, turi nurodyti kryptį (į kairę arba į dešinę) ir atstumą (kėdžių skaičių). Tada bus galima vienu metu pakelti vaikus ir kiekvienam nurodyti, kur atsisėsti.

Vaikų persodinimas sukelia chaosą. Kiekvienas vaikas paeina tam tikra atsumą (arba pasilieka savo vietoje). Apibrėžiama, kad chaosas lygus didžiausiam iš šių atstumų. Vaikus galima persodinti įvairiais būdais. Tėvai nori kiek galima mažesnio chaoso. Padėkite surasti tokį vaikų persodinimo būdą.

Pradiniai duomenys

Pirmoje eilutėje yra vienas sveikasis skaičius n ( $1\\len\\le10^6$ ). Antroje eilutėje yra n sveikųjų skaičių $p_1$ , $p_2$ , ..., $p_n$ . Skaičiai $p_1$ , $p_2$ , ..., $p_n$ yra aibės ${1,2,\\dots,n}$ perstatymas, nusakantis norimą vaikų susodinimo tvarką.

Rezultatai

Vienintelėje rezultatų eilutėje turi būti vienintelis skaičius: mažiausias chaosas.

Pavyzdys

Duomenys	Rezultatai
6 3 4 5 1 2 6	2

Šeštadieninė informatikos olimpiadininkų mokykla

Gimimo diena

Pradiniai duomenys

Rezultatai

Pavyzdys