34574번 - PIRAMIDA 다국어

문제

Mirko ima niz od $N$ prirodnih brojeva. Želi od njega napraviti piramidu. To je niz u kojem postoji neka pozicija $k$ 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 $N$ (1ドル ≤ N ≤ 500,円 000$), broj iz teksta zadatka.

U drugom je retku niz od $N$ prirodnih brojeva $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 = 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 1ドル$. poteza
• 9 8 8 9 12 12 11 ← nakon 2ドル$. poteza
• 8 9 8 9 12 12 11 ← nakon 3ドル$. poteza
• 8 8 9 9 12 12 11 ← nakon 4ドル$. poteza imamo piramidu.