1820: 逆序对(高难度版)
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
题目描述
猫猫 TOM 和小老鼠 JERRY 最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。
最近，TOM 老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中中ai>aj 且i<j 的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。注意序列中可能有重复数字。
输入格式
第一行，一个数n，表示序列中有n个数。
第二行n个数，表示给定的序列。序列中每个数字不超过int范围。
输出格式
输出序列中逆序对的数目
样例输入 复制
6
5 4 2 6 3 1样例输出 复制
11
提示
例如：序列 3 2 1 4
3>2 则3，2是一个逆序对
3>1 则3，1是一个逆序对
3<4 则3，4不是逆序对
2>1 则2，1是一个逆序对
2<4 则2，4不是逆序对
1<4 则1，4不是逆序对
所以一共有3个逆序对
3>2 则3，2是一个逆序对
3>1 则3，1是一个逆序对
3<4 则3，4不是逆序对
2>1 则2，1是一个逆序对
2<4 则2，4不是逆序对
1<4 则1，4不是逆序对
所以一共有3个逆序对