OJ现已增加邮箱找回密码功能，还没有绑定邮箱的同学们请抓紧时间，以免密码丢失无法找回


问题1239--逆序数

1239: 逆序数

时间限制: 1 Sec  内存限制: 128 MB
提交: 2554  解决: 1050
[提交] [状态] [讨论版] [命题人:]

题目描述

A为一个有n个数字的有序集 (1<=n<=1e5)，其中所有数字各不相同。
当存在正整数 i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j]，则 <A[i], A[j]> 这个有序对称为 A 的一个逆序对，也称作逆序数。
请问序列A中的逆序对有多少个。

输入

第一行，序列长度n。（1<=n<=1e5）
第二行，序列a[1]...a[n]。（a[i]<1e8）

输出

逆序对个数。

样例输入 Copy 

5
5 4 3 2 1

样例输出 Copy 

10

来源/分类

分治法 
[提交] [状态]