An inversion in an array is a pair of positions i < j with a[i] > a[j] (equal values are not an inversion). Write a program that counts the inversions of an array in O(n log n) time by modifying merge sort: the count is (inversions in the left half) + (inversions in the right half) + (split inversions counted during the merge).
Input. The first line holds n (0 ≤ n ≤ 200 000). The second line holds n integers.
Output. One line:
Inversions: X
Example. For the input
5
2 4 1 3 5
the output is
Inversions: 3
(the pairs 2 > 1, 4 > 1 and 4 > 3).
Use a long for the count: a reversed array of 200 000 elements has almost 2·10¹⁰ inversions. An O(n²) double loop is too slow for the largest inputs.