117. Count Inversions
Challenge1000 ms256 MBSolved by 0%
An inversion is a pair of positions (i, j) with i < j where
a[i] > a[j], a pair that is out of order.
Print how many inversions the array contains. A sorted array has none; a fully reversed one has the maximum possible.
Constraints - `1 ≤ n ≤ 200000` - `-1000000000 ≤ a[i] ≤ 1000000000`
Input
The first line contains an integer n.
The second line contains n space-separated integers.
Output
Print one integer, how many pairs of positions are out of order.
Input5
2 4 1 3 5
Output3
Notehas three out-of-order pairs
Input4
1 2 3 4
Output0
Noteis already sorted, so there are no inversions
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.