3. An inversion in an array A[1,...,n| is a pair of indices (i,j) such that i Aj]. The number of n (n -1)/2. (if the array is inversions in an n-element array is between 0 (if the array is sorted) and ( sorted backward). Describe and analyze an algorithm to count the number of inversions in an n-element array in O(n logn) time. [Hint: Modify mergesort]