inversiuni

Ludwig are o permutare $p = (p_1, p_2, \dots, p_N)$ a mulțimii $\{1, 2, \dots, N \}$ și o masă pe care putea așeza numerele din permutare. Ludwig ia primul număr din permutare, adică $p_1$, și îl așează pe masă. Al doilea număr, $p_2$, îl pune fie în stânga lui $p_1$, fie în dreapta lui $p_1$. La fiecare pas, dacă s-au așezat pe masă deja numerele $p_1, p_2, \dots, p_i$, atunci numărul $p_{i+1}$ este pus fie în stânga numerelor deja așezate, fie în dreapta lor.

Cerinţă

Ajutați-l pe Ludwig să determine o modalitate de așezare a întregii permutări pe masă astfel încât în final să se obțină o nouă permutare care are un număr minim de inversiuni.

Date de intrare

Fişierul inversiuni.in conţine pe prima linie numărul natural $N$, iar pe linia a doua, separate prin câte un spațiu, numerele $p_1, p_2, \dots, p_N$.

Date de ieșire

Fişierul inversiuni.out conţine un singur număr natural reprezentând numărul minim de inversiuni care se pot obține.

Restricții și precizări

• $1 \leq N \leq 200 \ 000$
• O inversiune în permutare este o pereche de indici $(i, j)$ cu $i < j$ și $p_i > p_j$. De exemplu, permutarea $p = (3, 2, 1, 4)$ are ca inversiune perechea de indici $(1, 3)$ pentru că $p_1 > p_3$; o altă inversiune este perechea de indici $(2, 3)$ pentru că $p_2 > p_3$.

Exemplul 1

inversiuni.in

4 
2 1 3 4

inversiuni.out

0

Explicație

Se așează elementele pe masă astfel:

$2$
$1 \ 2$ ($1$ este așezat la stânga)
$1 \ 2 \ 3$ ($3$ este așezat la dreapta)
$1 \ 2 \ 3 \ 4$ ($4$ este așezat la dreapta)

Se obține permutarea identică, adică zero inversiuni.

Exemplul 2

inversiuni.in

4 
2 1 4 3

inversiuni.out

1

Explicație

Se așează elementele pe masă astfel:

$2$
$1 \ 2$ ($1$ este așezat la stânga)
$1 \ 2 \ 4$ ($4$ este așezat la dreapta)
$1 \ 2 \ 4 \ 3$ ($3$ este așezat la dreapta)

Se obține o permutare care are o inversiune.