题目描述

对于一个长度为 $N$ 的整数序列 $A$，满足 $i < j$ 且 $A_i > A_j$ 的数对 $(i,j)$ 称为整数序列 $A$ 的一个逆序对。

请求出整数序列 $A$ 的所有逆序对个数。

输入格式

第一行为整数 $N\ (1 \le N \le 10^5)$。

第二行为 $N$ 个整数，表示长为 $N$ 的整数序列。

输出格式

输出逆序对的个数。

5
1 2 3 4 5

0

5
5 4 3 2 1

10

1
1

0