Manoj Attal manojattal

The answer is the number of inversions in the array, which is the number of pairs i,j such that i < j and a[i] > a[j]. Counting this is a fairly classical problem with many solutions such as using data structures such as Balanced Trees or Binary Indexed Trees. Another particularly elegant solution involves modifying merge sort to count the number of inversions when merging the two sorted halves in the algorithm.