DiffPush Tier Arrays · Hard O(N log N) · O(N)
A leaderboard rebuild produced a ranking whose entries should have followed increasing rank ids but came out partly shuffled. To estimate the disruption, the analytics job measures how many pairs of entries appear out of order relative to the intended ranking. Report that count over the whole list.
Input: An integer N and an array arr of N integers.
Output: The number of index pairs (i, j) with i < j and arr[i] > arr[j].
1 <= N <= 10^51 <= arr[i] <= 10^9The answer can reach about N^2 / 2Input: {"N":5,"arr":[2,4,1,3,5]}
Output: 3
The out-of-order pairs are (2,1), (4,1) and (4,3), giving three drifts from the intended order.
Input: {"N":5,"arr":[2,3,4,5,6]}
Output: 0
The ranking is already increasing, so no pair is out of order.