逆序对

题目描述

给定一个长度为 $n$ 的数组 $a$。如果存在一对下标 $i < j$ 满足 $a_i > a_j$，我们就称 $(i, j)$ 是一个逆序对。

请你统计数组中逆序对的总数。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$。

输出格式

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

样例

5
2 3 1 5 4

3

样例说明：逆序对为 (1,3), (2,3), (4,5)，共 3 个。

数据范围

$1 \le n \le 10^5$，$0 \le a_i \le 10^9$。

提示：答案可能达到 $\frac{n(n-1)}{2}$，请使用 64 位整数。