def countInversions(arr):
    return mergeSort(arr)

def mergeSort(arr):
    inversions = 0
    lenArr = len(arr)

    if lenArr > 1:
        #split array in two
        middle = lenArr // 2
        leftArr = arr[middle:]
        rightArr = arr[:middle]

        #sort halves
        inversions = mergeSort(leftArr) + mergeSort(rightArr)

        #init indexes
        leftIndex = 0
        rightIndex = 0
        currentIndex = 0

        #save len() calls
        lenLeftArr = len(leftArr)
        lenRightArr = len(rightArr)

        #compare subarrays
        while leftIndex < lenLeftArr and rightIndex < lenRightArr:
            if leftArr[leftIndex] < rightArr[rightIndex]:
                arr[currentIndex] = leftArr[leftIndex]
                leftIndex = leftIndex + 1
            else:
                arr[currentIndex] = rightArr[rightIndex]
                rightIndex = rightIndex + 1
                inversions = inversions + (lenLeftArr-leftIndex)
            currentIndex = currentIndex + 1

        #copy remaining elements from leftArr
        while leftIndex < lenLeftArr:
            arr[currentIndex] = leftArr[leftIndex]
            leftIndex = leftIndex + 1
            currentIndex = currentIndex + 1

        #copy remaining elements from rightArr
        while rightIndex < lenRightArr:
            arr[currentIndex] = rightArr[rightIndex]
            rightIndex = rightIndex + 1
            currentIndex = currentIndex + 1

    return inversions