Description

给定一个长度为 n的整数数列，请你计算数列中的逆序对的数量。 逆序对的定义如下：对于数列的第i个和第j个元素，如果满足 $i$<$j$ 且 $a[i]$ > $a[j]$，则其为一个逆序对；否则不是。

Input Format

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

Output Format

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

6
2 3 4 5 6 1

5

Hint

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

Source

2.1基础算法 归并排序