Code Submission Evaluation System Login

Algoritmit ongelmanratkaisussa 2019

Pyramidi


Task | Statistics


CSES - PyramidiCSES - Pyramidi

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
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]$.