题目描述

给定 $N$ 个整数构成一个序列： $A_1,A_2,\dots,A_N$。

请统计，这个序列中存在多少组逆序对。

所谓一组逆序对，是指序列中出现了两个元素，其大小与其顺序相悖。换个说法就是一组逆序对需要有两个下标 $i$ 与 $j$，满足 $i<j$ 且 $A_i>A_j$。

输入格式

• 第一行：单个整数表示 $N$
• 第二行到第 $N+1$ 行：$N$ 个整数表示 $A_1,A_2.\dots,A_N$

输出格式

4
314
15
926
53

3

数据范围

• $30\%$ 的数据，$1\leq N\leq 1,000$
• $60\%$ 的数据，$1\leq N\leq 20,000$
• $100\%$ 的数据，$1\leq N\leq 300,000$
• $-1,000,000,000\leq A_i\leq 1,000,000,000$