Inverzije

Podan je seznam $N$ števil $x_i$. Paru indeksov $i$ in $j$, kjer je $i<j$ in $x_i > x_j$, rečemo inverzija. Inverzije so torej pari števil, ki niso v pravem vrstnem redu (naraščajoče urejen seznam nima inverzij). Napišite program, ki bo učinkovito izračunal število inverzij v podanem seznamu.

Namig: razmislite o prilagoditvi algoritma merge sort.

Omejitve podatkov:

• $1 \leq N \leq 10^6$
• $0 \leq x_i \leq 10^9$

Vhodni in izhodni podatki:

V prvi vrstici je podana velikost seznama $N$. V drugi vrstici so po vrsti s presledkom ločena števila $x_1, x_2, \ldots, x_N$.

Izpišite število inverzij v seznamu.

Primer vhoda:

6
7 2 4 2 1 5

Pravilen izhod:

9