71. Count Inversions
HardMerge SortDivide and Conquer
An inversion is a pair i < j with a[i] > a[j]. Print the number of inversions.
Input format
Line 1: n Line 2: n integers
Output format
The number of inversions.
Example 1
Input
5 2 4 1 3 5
Output
3
Example 2
Input
3 1 2 3
Output
0
Constraints
1 ≤ n ≤ 10⁵
Read input from standard input and print the answer to standard output. Your code is judged against 7 test cases, most of them hidden.
Loading the MyLoginn IDE…