题目描述

给定一个长度为$n$的序列 $a_1,a_2,…,a_n$ ，定义它的逆序对数为：二元组$(i,j)$,满足$i < j$且$a[i]> a[j]$。要求统计逆序对数。

例如，数组 $(3,1,4,5,2)$ 的逆序对有 $(3,1),(3,2),(4,2),(5,2)$ ，共4个。

输入格式

第一行为$n$,表示序列长度，接下来的$n$行，第 $i+1$ 行表示序列中的第 $i$ 个数。

输出格式

所有逆序对总数。

4
3
2
3
2

3

数据范围与约定

$N≤10^5，a_i≤10^5$。