题目描述

给定一个包含 $n$ 个元素的数组 $a[i]$，其中每个元素的值保证在 $[1,n]$ 范围内。请你统计其中逆序对的数量。

我们称一对数对 $(i, j)$ 是一个逆序对，当且仅当 $1 \le i < j \le n$ 且 $a[i] > a[j]$。

例如数组 $[1,3,2,4]$ 有一个逆序对 $(3,2)$，而 $[3,4,1,2]$ 有四个逆序对 $(3,1),(3,2),(4,1),(4,2)$。

输入格式

第一行一个整数 $n$，表示数组的长度。

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示数组中的元素。

输出格式

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

4
3 4 1 2

4

数据规模与约定

对于 $100\%$ 的数据，$1 \le n \le 1×10^5$，$a_i \in [1,n]$。