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