Counting number of inversions. We are given a sequence of n distinct numbers a$1,...,$an$.$ We

define an inversion to be a pair i $<$ j such that ai $>$ aj

$.$ Give an O$($nlogn$)$ algorithm to count the number

of inversions. $($Hint: Consider modifying Merge Sort to return both the sorted array and the number of

inversions. Use recursion to sort and count the inversions of the two halves. Then, during the merging

process, count the number of inversions needed for the current recursive step.$)$