题目描述

给一个长为 $n$ 的序列 $a_1,a_2,\dots,a_n$，如果存在 $i<j$ 并且 $a_i>a_j$，那么我们称之为逆序对，求逆序对的数目。

输入格式

第一行为 $n$ ,表示序列长度，第二行 $n$ 个数，表示序列 $a_i$。

输出格式

所有逆序对总数。

样例输入

4
3 2 3 2

样例输出

3

数据范围

对于 $30\%$ 的数据，满足 $n\le5000$

对于 $100\%$ 的数据，满足 $n\le5\times 10^5,\left|a_i\right|\le10^9$