逆序对

题目描述

对于给定的一段正整数序列，逆序对就是序列中的一对整数 $(a_i, a_j)$，满足 $a_i > a_j$ 且 $i < j$。计算逆序对的数目。

输入格式

第1行一个数 $n$（$n \le 2500$）；第2行 $n$ 个数，每个数字不超过 $10^9$。

输出格式

输出序列中逆序对的数目。

样例输入 #1

6
1 2 3 3 5 6

样例输出 #1

0

样例输入 #2

5
5 1 1 0 4

样例输出 #2

6

数据范围

$n \le 2500$，数字不超过 $10^9$。

知识点与难度

本题涉及的知识点从属于 GESP 4级（排序），难度等级：⭐⭐⭐。

测试点分布