def countInversions(arr):
    def merge_sort_and_count(arr):
        if len(arr) <= 1:
            return arr, 0
        
        mid = len(arr) // 2
        left, left_inversions = merge_sort_and_count(arr[:mid])
        right, right_inversions = merge_sort_and_count(arr[mid:])
        
        merged, split_inversions = merge_and_count(left, right)
        
        total_inversions = left_inversions + right_inversions + split_inversions
        return merged, total_inversions
    
    def merge_and_count(left, right):
        res = []
        i = j = 0
        inversions = 0
        
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:  
                res.append(left[i])
                i += 1
            else: 
                res.append(right[j])
                j += 1
                inversions += len(left) - i  
        
        res.extend(left[i:])
        res.extend(right[j:])
        
        return res, inversions
    
    _, total_inversions = merge_sort_and_count(arr)
    return total_inversions