该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

输入格式

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

输出格式

所有逆序对总数。

样例

输入样例

4
3 2 3 2

输出样例

3

数据范围与提示

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

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