逆序对问题

一、题目描述

给定一个序列$a_1, a_2, \cdots, a_n$，若存在$i < j$且$a_i > a_j$，则称$a_i, a_j$为逆序对，需要求出该序列中逆序对的总数。

二、输入

• 第一行：输入一个整数$n$，表示序列的长度，满足$1 \leq n \leq 10^5$。
• 接下来的$n$行：每行输入一个整数，按顺序表示序列中的元素$a_1, a_2, \cdots, a_n$，且$a_i$满足$0 \leq a_i \leq 10^5$。

三、输出

• 输出一个整数，该整数表示输入序列中逆序对的总数。

四、输入样例

4
3
2
3
2

五、输出样例

3

六、提示

$1 \leq n \leq 10^5$ $1 \leq a_i \leq 10^5$

七、来源

一本通在线评测