题目描述

给定长度为$n$的序列$a_i$，定义逆序对为这样的有序数对$(i,j)$：对于$i<j$，有$a_i>a_j$。

求序列有多少逆序对。

输入格式

第一行输入一个整数$n$。 第二行输入$n$个整数$a_i$。

输出格式

输出一行一个整数，表示你的答案。

样例输入 #1

4
3 4 2 1

样例输出 #1

5

说明/提示

对于40%的数据，有$1\leq n\leq 1000$。 对于100%的数据，有$1\leq n\leq 10^5,1\leq a_i\leq 10^9$。