PIRAMIDA

시간 제한1초메모리 제한2048 MB

요약

주어진 수열을 인접한 원소를 교환하는 연산만으로 단조 증가 후 단조 감소하는 피라미드 형태로 바꾸는 최소 교환 횟수를 구한다.

난이도: 보통10점 중 7점
유형: 정렬, 그리디, 이분 탐색
정답자: 아직 제출이 없습니다

문제

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.

예제3

예제 1
입력
```
4
1 5 9 14
```
예상 출력
```
0
```
예제 2
입력
```
7
9 9 8 8 12 12 11
```
예상 출력
```
4
```
예제 3
입력
```
3
2 1 3
```
예상 출력
```
1
```