• 1 <= nums.length <= 5 * 10⁴
• -2³¹ <= nums[i] <= 2³¹ - 1

A Reverse Pair is a specific type of inversion where the left element is more than twice the value of the right element. Our goal is to count how many such pairs exist without checking every possible combination one by one.

The most straightforward approach is to use two nested loops to compare every element with every element that comes after it. This takes O(N²) time, which is too slow for an array of 50,000 elements.

def count_reverse_pairs(nums):
    count = 0
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            # Check the specific "reverse pair" condition
            if nums[i] > 2 * nums[j]:
                count += 1
    return count

To improve efficiency, we can use a Divide and Conquer strategy similar to Merge Sort. If we split the array into two halves, the total number of reverse pairs is the sum of:
1. Reverse pairs entirely in the Left half.
2. Reverse pairs entirely in the Right half.
3. Cross-Pairs: Pairs where the first element is in the Left half and the second is in the Right half.

By sorting the halves as we go, we can count these "cross-pairs" much faster than a linear scan.

The magic happens during the merge phase. Suppose we have two sorted halves, L and R. For a fixed element L[i], we want to find how many elements R[j] satisfy L[i] > 2 * R[j].

Because L is sorted, as we move from L[i] to L[i+1], the value increases. This means any R[j] that was "beaten" by L[i] will definitely be beaten by L[i+1]. We only need to move our j pointer forward, never backward!

# Counting cross-pairs between sorted halves L and R
count = 0
j = 0
for i in range(len(L)):
    # Keep moving j while the condition holds
    while j < len(R) and L[i] > 2 * R[j]:
        j += 1
    # All elements in R from index 0 to j-1 are valid pairs for L[i]
    count += j

We integrate the counting logic directly into the Merge Sort process. We must count the pairs before merging the halves, as the merge step will shuffle their relative order.

def merge_sort_and_count(nums, start, end):
    if start >= end:
        return 0
    
    mid = (start + end) // 2
    # Recursively solve for sub-problems
    count = merge_sort_and_count(nums, start, mid) +             merge_sort_and_count(nums, mid + 1, end)
    
    # 1. Count Cross-Pairs using the two-pointer trick
    j = mid + 1
    for i in range(start, mid + 1):
        while j <= end and nums[i] > 2 * nums[j]:
            j += 1
        count += (j - (mid + 1))
    
    # 2. Standard Merge step to keep halves sorted
    nums[start:end+1] = sorted(nums[start:end+1])
    return count

The other reverse pair (3, 1) was already counted during the recursive call on the right half [3, 1].
Total Reverse Pairs = 1 (Recursive) + 1 (Cross) = 2.