Problem H: Recursion / Divide and Conquer - The Number of Inversions

上一题 正确率: $82.45\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $302$ 正确数量 $249$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 STL 排序

Description

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.

Input

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.

Output

Print the number of inversions in a line.

Sample Input复制

5
3 5 2 1 4

Sample Output复制

6

提示

1≤n≤200,000

0≤ai≤10^9

ai are all different