给定一个长度为 $n$ 的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第 $i$ 个和第 $j$ 个元素，如果满足 $i < j$ 且 $a[i] > a[j]$，则其为一个逆序对；否则不是。

输入格式

第一行包含整数 $n$，表示数列的长度。

第二行包含 $n$ 个整数，表示整个数列。

输出格式

输出一个整数，表示逆序对的个数。

数据范围

$1 \le n \le 100000$，
数列中的元素的取值范围 $[1,10^9]$。

输入样例：

6
2 3 4 5 6 1

输出样例：

5

已按 OJ 可直接使用的 1.in/1.out ... 25.in/25.out 生成 25 组“逆序对数量”测试数据（覆盖：有序/逆序、重复值、极值、奇数长度、n=100000 压力、以及 64 位溢出专杀用例等）。

下载测试数据（zip）

下面按 1..25 逐组说明每组主要在卡哪些常见错误做法（正确解法通常是归并排序计数/树状数组离散化，计数必须用 64 位）：

1. 样例：基础正确性（末尾一个最小值，逆序对=5）。
2. n=1：边界（输出 0）。
3. 完全升序：逆序对=0；卡把“>=”当“>”或公式乱算。
4. 完全逆序（20）：逆序对=190；卡计数公式、合并计数逻辑。
5. 全相等：逆序对=0；卡把相等也算逆序（写成 >=）。
6. 小值域大量重复（1..5）：卡重复值处理、离散化/树状数组中“相等是否计入”。
7. 高低交替（1 与 1e9）：卡大量交错逆序；也卡 O(n^2) 暴力会慢。
8. 含极值与接近极值：卡比较器用减法溢出（某些语言）以及计数正确性。
9. 近乎有序 + 少量交换：卡细节 bug（merge 的 i/j 边界、计数加的数量是否正确）。
10. 随机 n=1000：综合正确性。
11. 非递减且含重复块（应为 0）：卡误把“相等”算逆序；也卡树状数组查询范围写错。
12. 降序重复块（每值重复 3 次）：卡重复+逆序组合（相等不算，但跨值算），很容易算错。
13. 999 个大数 + 末尾 1..10：逆序对巨大且结构清晰；卡“只统计相邻逆序”这类错法。
14. 1..10 在前 + 999 个大数在后：逆序对应为 0；卡错误地以为“有大有小就有逆序”或写反比较方向。
15. 奇数长度 n=999 随机：卡归并分治边界（mid、区间拷贝）与 off-by-one。
16. n=100000 升序（压力）：逆序对=0；强卡性能（暴力 O(n^2) 会炸），也卡不该溢出。
17. n=100000 逆序（压力）：逆序对= n(n-1)/2 = 4,999,950,000；强卡 64 位（32 位必溢出）。
18. n=100000 全相等（压力）：逆序对=0；强卡重复值处理与性能。
19. n=100000 小值域 1..100（压力）：强卡重复值 + 性能；也卡树状数组/离散化实现。
20. n=100000 全范围随机（压力）：综合强测（性能+正确性）。
21. “风琴形” 1..50000..1：卡结构化大量逆序（右半递减产生大量逆序）；归并/树状数组错一点就很明显。
22. 锯齿序列（奇偶交错）：逆序对非常多且分布复杂；卡实现细节和性能。
23. 专卡“<= vs <”合并比较（重复值） [2,2,2,1,1,1]：相等不算逆序，但跨 2>1 算；错误合并条件常导致计数偏差。
24. n=70000 逆序（溢出专杀）：逆序对约 2.449e9，超过 2^31-1；强卡用 int 存答案会溢出。
25. 50000 个 1e9 后接 50000 个 1（块状）：逆序对= 50,000*50,000 = 2,500,000,000；强卡 64 位 + 结构化大计数。

接下来你继续给题，我都会：

• 生成 k.in/k.out 的 zip
• 并按编号逐组说明“卡什么错误做法”。