PIRAMIDA

문제

Mirko ima niz od $NN$ prirodnih brojeva. Želi od njega napraviti piramidu. To je niz u kojem postoji neka pozicija $kk$ za koju vrijedi A_1 ≤ \dots ≤ A_{k-1} ≤ A_k ≥ A_{k+1} ≥ \dots ≥ A_n. Drugim riječima, želi ulazni niz prepraviti tako da do neke pozicije svaki element bude veći ili jednak prethodnom, a nakon te pozicije svaki bude manji ili jednak prethodnom. U jednom potezu može zamijeniti dva susjedna elementa niza. Koliko najmanje poteza mu je potrebno da ulazni niz pretvori u piramidu?

입력

U prvom je retku prirodan broj $NN$ (1 ≤ N ≤ 500\, 000), broj iz teksta zadatka.

U drugom je retku niz od $NN$ prirodnih brojeva $A_{i}A\_i$ (1 ≤ A_i ≤ 10^9), niz iz teksta zadatka.

출력

Prirodan broj iz teksta zadatka.

힌트

Opis prvog probnog primjera: Niz je rastući tj. piramida jer za poziciju $k=4k\; =\; 4$ vrijedi traženi uvjet.

Opis drugog probnog primjera: Niz možemo pretvoriti u piramidu u četiri poteza. Npr. ovako:

• 9 9 8 8 12 12 11 ← početni niz
• 9 8 9 8 12 12 11 ← nakon $11$. poteza
• 9 8 8 9 12 12 11 ← nakon $22$. poteza
• 8 9 8 9 12 12 11 ← nakon $33$. poteza
• 8 8 9 9 12 12 11 ← nakon $44$. poteza imamo piramidu.

4
1 5 9 14

0

7
9 9 8 8 12 12 11

4

3
2 1 3

1