1119: 逆序数对

Memory Limit：128 MB Time Limit：1.000 S Judge Style：Text Compare Creator：
Submit：131 Solved：30

Description

在数列a1,a2,⋯,an中，出现 i<j 且 ai>aj 的情况，则称 (ai, aj) 是数列中的一个逆序对。常见的问题是统计逆序对的个数。


不允许普通用户打印题目，请教师登录后使用。如有疑问请联系管理员!

Input

共两行。
第一行，一个数字n，给出数列中元素的个数。1<=n<=100000
第二行，n个数字a1,a2,⋯,an，代表数列。

Output

一行，输出逆序对个数。

Sample Input Copy 

6
13 8 5 3 2 1

Sample Output Copy 

15

HINT

样例输入2

6
3 3 3 2 2 2


样例输出2:


9

Source/Category