Hardsortingarrays
Count Inversions
Time limit 2 s · Memory 64 MBAcceptance: —Solved by: 0
Statement
The first line contains n, the second line contains n integers. Print the number of inversions: pairs (i, j) with i < j and a_i > a_j.
Examples
Example 1
Input
5 2 4 1 3 5
Output
3
Example 2
Input
3 1 2 3
Output
0
Constraints
- 1 ≤ n ≤ 10^5
- -10^9 ≤ a_i ≤ 10^9