ArrayDivide and ConquerMerge Sort
An inversion is a pair of positions i < j with a[i] > a[j]. Count the inversions in the array. A sorted array has none; a reversed one has the most.
Input
Line 1: n. Line 2: n integers.
Output
Print the number of inversions.
Constraints
1 <= n <= 5 * 10^4 -10^9 <= each value <= 10^9
Example 1
Input
5 2 4 1 3 5
Output
3
The inversions are (2,1), (4,1) and (4,3).
Example 2
Input
5 5 4 3 2 1
Output
10
Every pair is inverted: 10 in total.