Count Inversions
mediumPlacement Coding+20 XPTime limit 2s
An inversion is a pair of positions i < j with a[i] > a[j] — two elements that are in the wrong order. Count the inversions. (It measures how far the array is from being sorted.)
Input:
- line 1:
n - line 2:
nintegers
Output: the number of inversions (up to about 5·10⁹ — use 64-bit integers).
Constraints: 1 ≤ n ≤ 10⁵, 1 ≤ values ≤ 10⁹.
Think about it: modify merge sort. While merging two sorted halves, when an element from the right half is placed before the remaining elements of the left half, it forms an inversion with each of them — add that count all at once.
Sample input 1
5 2 4 1 3 5
Sample output 1
3
Sample input 2
3 1 2 3
Sample output 2
0
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).