题目描述

给定一个序列 $a$，如果存在 $i<j$ 并且 $a_i>a_j$，那么我们称 $(i, j)$ 为一个逆序对。

求序列 $a$ 中逆序对的个数。

输入格式

输入的第一行包含一个整数 $n$，代表序列长度。

接下来包含 $n$ 行，第 $i$ 行代表序列中的第 $i$ 个数 $a_i$。

输出格式

输出一行一个整数，代表序列 $a$ 中逆序对的个数。

4
3
2
3
2

3

数据规模与约定

对于全部的测试点，保证 $1 \leq n \leq 10 ^ 5$，$1 \leq a_i \leq 10^5$。