题目描述

给定一个序列 $a_1, a_2, \dots, a_n$，如果存在 $i<j$ 且 $a_i > a_j$，则称 $(i, j)$ 为一个逆序对。求逆序对的总数。

输入格式

第一行一个整数 $n$，表示序列长度。
接下来 $n$ 行，每行一个整数，依次表示序列中的每个数。

输出格式

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

样例

4
3
2
3
2

3

数据范围

• $n < 100000$
• $0 \le a_i \le 10^6$