In this problem, your goal is to compute the number of inversions in an input array. For an array A of size n, we say the a pair of indices (i,j) into the array is an inversion if i < j and A[i] > A[j]. For example, consider the following array:

arr = array.array('i',[2,3,8,6,1])

This array has 5 inversion: (8,6), (8,1), (2,1), (3,1), and (6,1). A simple solution is to consider every possible pair of indices.

def naiveCountInversion(arr): n = len(arr) count = 0 for i in range(n): for j in range(i,n): if arr[i] > arr[j]: count += 1 return count

naiveCountInversion(arr)

Output: 5

However, this is a naive solution in O(n * n).

**Problem:** Devise and implement an algorithm that solves the inversion problem in O(n log n).

def countInversions(arr): pass