Se citeste un vector cu n numere intregi. Determinati numarul de inversiuni ale vectorului, adica numarul de perechi de pozitii (i, j) cu i < j si a[i] > a[j], folosind o varianta a algoritmului Merge Sort (Divide et Impera) care numara inversiunile chiar in timpul interclasarii, fara a compara toate perechile de elemente.
- Date de intrare
- Pe prima linie se citeste numarul natural n. Pe a doua linie se citesc cele n numere intregi ale vectorului, separate prin spatiu.
- Date de iesire
- Se afiseaza numarul de inversiuni ale vectorului.
- Restrictii
- 1 <= n <= 100000, -10^9 <= a[i] <= 10^9
Exemple
Exemplul 1
Intrare
1 5
Iesire
0
Exemplul 2
Intrare
5 5 4 3 2 1
Iesire
10