The Number of Inversions
For a given sequence A={a0,a1,...an−1}, the number of pairs (i,j)where ai>aj and i<j,is called the number of inversions.The number of inversions is equals to the number of swaps of Bubble Sort defined in the following program:
bubbleSort(A)
cnt = 0 // the number of inversions
for i = 0 to A.length-1
for j = A.length-1 downto i+1
if A[j] < A[j-1]
swap(A[j], A[j-1])
cnt++
return cnt
For the given sequence A, print the number of inversions of A. Note that you should not use the above program, which brings Time Limit Exceeded.