def count_inversions_recursive(arr):
    if len(arr) <= 1:
        return arr, 0
    mid = len(arr) // 2
    p = arr[0:mid]
    q = arr[mid:]

    a, inversion_p = count_inversions_recursive(p)
    b, inversions_q = count_inversions_recursive(q)
    c, cross_inversions = _count_cross_inversions(a, b)

    num_inversions = inversion_p + inversions_q + cross_inversions
    return c, num_inversions