Count inversions
Your task
Given an integer array nums, count the number of inversions: pairs (i, j) with i < j and nums[i] > nums[j]. Array length is up to 1e5, so an O(n^2) approach will time out. Return the count as an integer.
Examples
count_inversions(nums: list[int]) -> intExample 1
Input
count_inversions([2, 4, 1, 3, 5])Output
3