Rezolvare PBinfo #3206

Se dă șirul a1, a2, …, an care este o permutare a mulțimii {1, 2, ..., n}. O inversiune în permutare este o pereche (i, j) cu proprietatea că i < j și a[i] > a[j].

Cerința

Să se determine numărul inversiunilor permutării.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații, reprezentând permutarea.

Date de ieșire

Programul va afișa pe ecran numărul S, reprezentând numărul inversiunilor permutării.

Restricții și precizări

• 1 ≤ n ≤ 100.000

Exemplu:

Intrare

5
4 2 5 1 3

Ieșire

6

Explicație

Cele 6 inversiuni sunt date de perechile de indici (1,2), (1,4), (1,5), (2,4), (3,4), (3,5).