def _inversions(xs):
    # Can't be unsorted
    if len(xs) < 2: return 0, xs

    # Divide into two subarrays
    leng = len(xs)//2
    left = xs[:leng]
    right = xs[leng:]

    # Perform recursive call
    lcount, left = _inversions(left)
    rcount, right = _inversions(right)

    # Reverse the lists to allow O(1) pop.
    # Since we already have an O(n) copy,
    # this doesn't increase complexity.
    left.reverse()
    right.reverse()

    # Merge by popping
    count = 0
    total = []
    while left != [] and right != []:
        if left[-1] <= right[-1]:
            total.append(left.pop())
        else:
            total.append(right.pop())
            count += len(left)

    # Add elements from non-empty array,
    # if applicable.
    left.reverse()
    right.reverse()
    total += left + right
    return (count + lcount + rcount), total

def num_inversions(xs):
    count, _ = _inversions(xs)
    return count