Count Inversions

An inversion is a pair of positions i < j where nums[i] > nums[j]: a bigger number standing in front of a smaller one. A sorted list has no inversions, and a list in reverse order has as many as possible. Write count_inversions(nums) that returns how many inversions nums has. Equal numbers never form an inversion.

Examples

count_inversions([3, 1, 2])      # returns 2
count_inversions([1, 2, 3, 4])   # returns 0
count_inversions([4, 3, 2, 1])   # returns 6
count_inversions([2, 2, 1])      # returns 2

In [3, 1, 2] the pairs (3, 1) and (3, 2) are out of order, while (1, 2) is fine.

Constraints

• 0 <= len(nums) <= 1,000
• -10^9 <= nums[i] <= 10^9

Note

Checking every pair passes these tests, but a list of a million numbers has about 500 billion pairs. The real goal is a count that grows like n log n, which handles that list in seconds.