An out-of-order pair in a list nums is a pair of indices i < j with nums[i] > nums[j]. Return the number of such pairs. Equal values never form a pair.
Examples
Input: nums = [2, 4, 1, 3, 5]
Output: 3
Explanation: (2,1), (4,1) and (4,3).
Input: nums = [3, 3, 1]
Output: 2
Explanation: Both 3s are before the 1; the two 3s do not count against each other.
Constraints
0 <= len(nums) <= 4 * 10**4-10**9 <= nums[i] <= 10**9- Target complexity: O(n log n). Checking every pair is too slow for the largest inputs.
Goals
- Count pairs (i < j) with nums[i] > nums[j] faster than O(n^2)
- Augment merge sort so the merge step counts crossing pairs
- Handle duplicates: equal values are not out of order