题目描述

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

用户并不需要知道精确的移动次数，实质上，大多数人都是凭感觉来认定这一列物品的混乱程度。根据 SORT 公司的经验，人们一般是根据“逆序对”的数目多少来称呼这一序列的混乱程度。假设将序列中第 $i$ 件物品的参数定义为 $A_i$，那么排序就是指将 $A_1, A_2, ...，A_n$ 从小到大排序。若 $i \lt j$ 且 $A_i \gt A_j$，则就为一个“逆序对”。

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

输入格式

第一行为$n$ ( $1 \le n \le 100000$ )。

接下来是 $n$ 行，每行一个长整型范围内的整数。

输出格式

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

样例

5
3
1
4
5
2

4