Imran suspects the line has never been properly sorted — he wants to know exactly how many pairs of players are "out of order" relative to a fully sorted arrangement. Read N integers. Count the number of pairs (i<j) such that a[i] > a[j] (inversions). Use merge-sort-based counting for O(N log N), not O(N^2).
Input
Line1: N. Line2: N integers.
Output
Total number of inversions.
Constraints
1 ≤ N ≤ 10^5
Sample Input
5 2 4 1 3 5
Sample Output
3
main.c
Loading editor…
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.