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.

In the first line, an integer n, the number of elements in A, is given. In the second line, the elements ai (i=0,1,..n−1) are given separated by space characters.

Print the number of inversions in a line.

5
3 5 2 1 4

6

1≤n≤200,000

0≤ai≤10^9

ai are all different