Two judges ranked the same items, and the second judge's ordering is described by a sequence of n rating values. The disagreement between the judges is measured by the number of inversions: the count of index pairs (i, j) with i < j but value[i] > value[j]. Report that count. Values may repeat; a tie (value[i] == value[j]) is NOT an inversion.
Line 1: an integer n.
Line 2: n space-separated integers, the rating values.
A single integer: the number of inversions.
Example 1
Input
5 3 1 2 4 1
Expected
5
Explanation
The out-of-order pairs are (3,1),(3,2),(3,1),(2,1),(4,1) -> 5 inversions.
Example 2
Input
4 1 2 3 4
Expected
0
Explanation
The sequence is already ascending, so there are 0 inversions.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →