题目描述

一次编程比赛后，$n$ 名选手排成一排，第 $i$ 名选手（从左到右）的得分是整数 $a_i$。

教练想知道队伍有多"乱"。他定义逆序对为满足下面两个条件的有序下标对 $(i, j)$：

• $i < j$（$i$ 在 $j$ 的左边）；
• $a_i > a_j$（左边这位选手的得分严格大于右边那位）。

请你求出队伍中逆序对的总数。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1, a_2, \ldots, a_n$，相邻两个整数之间用一个空格隔开。

输出格式

一行一个整数，表示逆序对的总数。

3
3 1 2

2

5
5 4 3 2 1

10

4
2 2 1 1

4

数据范围与提示

【样例 1 解释】

得分序列是 $3, 1, 2$。逐个检查下标对：

• $(1,2)$：$3 > 1$，是逆序对；
• $(1,3)$：$3 > 2$，是逆序对；
• $(2,3)$：$1 < 2$，不是。

共有 $2$ 个逆序对，输出 2。

【样例 2 解释】

序列严格递减，任何一对 $(i, j)$（$i < j$）都满足 $a_i > a_j$，共有 $\frac{5\times 4}{2} = 10$ 个逆序对。

【样例 3 解释】

序列是 $2, 2, 1, 1$。注意相等不算逆序对，所以 $(1,2)$ 与 $(3,4)$ 都不是逆序对；真正构成逆序对的是 $(1,3),(1,4),(2,3),(2,4)$，共 $4$ 个，输出 4。

【数据范围】

对于所有测试数据，保证：

• $1 \le n \le 2\times 10^5$；
• $-10^9 \le a_i \le 10^9$。

注意：逆序对总数最多为 $\frac{n(n-1)}{2} = 19999900000$，远超 int 的表示范围，计数的变量请使用 long long。

提示：从左到右扫描，扫到 $a_j$ 时它贡献的逆序对数是"已经出现过的、比它大的元素个数"。由于值域高达 $10^9$，先把所有取值离散化（排序去重后换成排名），再用树状数组维护"每个排名出现过多少次"，单次查询与修改都是 $O(\log n)$。用归并排序统计逆序对同样可行。

测试点编号	$n \le$	特殊性质
$1$		无
$2$	$2$	A
$3$		B
$4$	$3$	无
$5$		B
$6$	$10$	无
$7$	$100$
$8$		A
$9$	$1000$	B
$10$		无
$11$		C
$12$	$2000$	无
$13$	$5000$
$14$		D
$15$	$20000$	无
$16$		B
$17$	$2\times 10^5$	无
$18$		B
$19$		C
$20$		D

• 特殊性质 A：序列严格递增（$a_1 < a_2 < \cdots < a_n$），此时逆序对个数一定是 $0$。
• 特殊性质 B：序列严格递减，此时逆序对个数取到最大值 $\frac{n(n-1)}{2}$。
• 特殊性质 C：所有 $a_i$ 相等，此时一个逆序对也没有（相等不算逆序对）。
• 特殊性质 D：值域很小（$0 \le a_i \le 10$），出现大量相等元素，可以不离散化而直接用桶。