247. Count the Inversions
An inversion is a pair of positions i < j where a[i] > a[j]: two values
that are in the wrong order relative to each other.
Print how many inversions the array has.
The count measures how far from sorted the array is. A sorted array has none,
and a reversed one has every pair, n(n-1)/2.
Checking every pair is O(n^2) and the largest test rules it out. The trick
is that merge sort already discovers exactly this: when the merge step takes a
value from the right list while k values remain in the left, those k
values are each greater than it, so that is k inversions found at once.
Constraints - `1 ≤ n ≤ 200000` - `-1000000000 ≤ a[i] ≤ 1000000000`
Input
The first line contains an integer n.
The second line contains n integers.
Output
Print one integer, the number of inversions.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.