#1510. 排序工作量

排序工作量

题目描述

Sort公司是一个专门提供排序服务的公司,该公司的宗旨是:“顺序是最美丽的”。他们的工作是通过一系列移动,将某些物品按顺序摆好。他们的服务是通过工作量来计算的,即移动东西的次数。所以,在工作前必须考察工作量,以便向用户提出收费数目。

用户并不需要知道精确的移动次数,实质上,大多数人都是凭感觉来认定这一列物品的混乱程度。根据sort公司的经验,人们一般是根据“逆序对”的数目多少来称呼这一序列的混乱程度。假设将序列中第i\red{i}件物品的参数定义为Ai\red{A_{i}},那么排序就是指将A1,,An\red{A_{1} ,…,A_{n}}从小到大排序。若i<j,Ai>Aj\red{i<j, A_{i} >A_{j}},则<i,j>\red{<i,j>}就是一个“逆序对”。

Sort公司请你写一个程序,在尽量短的时间内,统计出“逆序对”的数目。

输入格式

共两行,第一行一个整数n(1n200000)\red{n(1≤n≤200000)},代表物品的总件数,接下来是n\red{n}个小于200000000\red{200000000}的正整数。

输出格式

一个整数,即的“逆序对”数目。

样例

输入样例

5
3 1 4 5 2

输出样例

4

提示

[3,1,4,5,2]\red{[3,1,4,5,2]}的逆序对有(3,1),(3,2),(4,2),(5,2)\red{(3,1),(3,2),(4,2),(5,2)}4\red{4}个。