Count the Inversions

Difficulty: 1600 4000 ms 128 MB

divide-and-conquer sorting

Count the pairs i < j with a_i > a_j.

Input: the first line has N; the second line has N integers.

Output: the number of inversions.

Constraints:

• 1 ≤ N ≤ 10⁵
• −10⁹ ≤ a_i ≤ 10⁹

Sample Tests

5
2 4 1 3 5

3

3
3 2 1

3

Read the Editorial