题目大意：给定一个序列a1,a2,a3,……,an,如果存在i<j，并且ai>aj,那么我们称之为逆序对，求给定序列中逆序对的数目。

输入

输出

样例输入

4
3
2
3
2

样例输出

3

提示

解题思路

利用树状数组能够快速计算前缀和的特点，统计前面i个数字出现了多少次。进来一个数字i，则相当于“a[i]”加1，即jia(i, 1)，统计前面i个数字出现的次数之和，即he(i)。求逆序对的总数，可以分解成以每个数字结尾的逆序对的个数之和。第i个数字是j，那么以数字j结尾的逆序对有多少个呢？就要看前面的数字有多少个比j大的——前面共有i个数，不大于j的个数是he(j)，因此j结尾的逆序对个数就是i – he(j)。（归并排序实现方法）

程序实现