Problem1707--逆序对

1707: 逆序对

[Creator : ]
Time Limit : 1 sec  Memory Limit : 128 MB

Solved: 9Submit: 27Statistics

Description

对于给定的一段正整数序列，逆序对就是序列中ai>aj且i<j的有序对。给定的一段正整数序列，求其中逆序对的数目。

Input

第一行，一个数n，表示序列中有n个数。

第二行n个数，表示给定的序列。序列中每个数字不超过10^9

对所有数据，n<=5*10^5


Output

给定序列中逆序对的数目。

Sample Input Copy 

6
5 4 2 6 3 1

Sample Output Copy 

11

HINT

归并排序/树状数组

Source/Category

 
Submit