题目描述

给定一个整数序列$a_1,a_2,…,a_n$，如果存在$i < j $ 并且$ a_i > a_j$，那么我们称之为逆序对。

求逆序对的数目

输入格式

第一行为n,表示序列长度；

接下来的n行，第i+1行表示序列中的第i个数。

输出格式

所有逆序对总数.

样例数据

input

4
3
2
3
2

output

3

数据规模与约定

保证$ 1 \leq n,a_i \leq 10^5$

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$