2305 - 逆序对

通过次数

10

提交次数

27

时间限制 : 1 秒
内存限制 : 128 MB

在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。

输入

第一行包含一个整数n,表示数组中的元素个数。其中1 ≤ n ≤ 10^5。 

第二行包含n个整数,每个元素均为int类型。

输出

输出一个整数,表示数组中的逆序对的总数。

样例

输入

4
7 5 6 4

输出

5

提示

【样例解释】

数组中一共有5组逆序对,它们分别为:

( 7 , 5 )

( 7 , 6 )

( 7 , 4 )

( 5 , 4 )

( 6 , 4 )

【数据规模】

50% 的数据,满足 1≤n≤1000;

100%的数据,满足 1≤n≤100000。