逆序对2

题目描述

有 $n$ 个数 $a_1, a_2, \dots, a_n$，对于其中的两个数字 $x, y$，如果满足 $x$ 出现的位置在 $y$ 出现的位置前面并且 $x$ 比 $y$ 大，则称 $(x,y)$ 为数组 $a$ 的一个逆序对。请问数组 $a$ 的逆序对一共有多少个？形式化的说，请求出有多少组 $(i,j)$ 满足 $i < j$ 并且 $a_i>a_j$。

输入格式

第一行一个整数 $n$。

接下来一行 $n$ 个整数，$a_1, a_2, \dots, a_n$。

输出格式

一行一个数，表示答案。

样例输入

4
4 2 3 1

样例输出

5

样例解释

5 个逆序对分别为 $(4,2),(4,3),(4,1),(2,1),(3,1)$。

数据范围

对于 $100\%$ 的数据，保证 $2\leq n\leq 100000, 1\leq a_i\leq n$ 并且每个数字都只会出现一次。