- Time limit: 1.00 s
- Memory limit: 512 MB
Sinulla on taulukko, jossa on n eri kokonaislukua. Jokaisella askeleella voit vaihtaa keskenään kaksi vierekkäistä lukua.
Haluat muuttaa taulukkoa niin, että siitä tulee pyramidi. Tämä tarkoittaa, että taulukko on ensin kasvava ja sitten laskeva. Lisäksi haluat löytää ratkaisun, jossa vaihtojen määrä on pienin mahdollinen.
Huomaa, että pyramidi saa olla myös kokonaan kasvava tai laskeva (eli toinen osuus voi olla tyhjä).
Syöte
Syötteen ensimmäisellä rivillä on kokonaisluku n: taulukon koko.
Seuraavalla rivillä on n eri kokonaislukua x_1,x_2,\dots,x_n: taulukon sisältö.
Tuloste
Tulosta yksi kokonaisluku: pienin vaihtojen määrä.
Rajat
- 1 \le n \le 2 \cdot 10^5
- 1 \le x_i \le 10^9
Esimerkki
Syöte:
4 2 1 5 3
Tuloste:
1
Selitys: Sinun riittää vaihtaa keskenään kaksi ensimmäistä lukua, jolloin tuloksena on pyramidi [1,2,5,3].