1803: 逆序对有多少

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：51 Solved：19

Description

       学校的数学俱乐部，最近玩起了”逆序对”的纸牌游戏。桌上从左到右一排纸牌共有n张，比赛看谁先算出这一排数字序列中逆序对的数目。注意数字可能有重复的。
        “逆序对”就是序列中 a[i]>a[j] 且 i<j的有序对。

Input

第一行输入 n。第二行共有 n个正整数(<=10^7) ，数字间空格分隔。

Output

输出一个正整数，为逆序对的数目。

Sample Input Copy 

6
5 4 2 6 3 1

Sample Output Copy 

11

HINT

n