题目描述

给出一段正整数序列 $A$，求其中的逆序对有多少组。

定义一组逆序对为：一对 $A_i,A_j$，使得 $A_i > A_j$ 且 $i < j$。

输入格式

第一行一个正整数 $n$ ，表示序列中的数字个数。

第二行 $n$ 个正整数 $A_1 \sim A_n$，使用空格分隔。

输出格式

一个正整数 $x$ ，表示逆序对的数量。

样例输入输出

5
5 3 4 1 2

8

说明/提示

样例解释 #1

样例中的逆序对包括 $5\ 3,5\ 4,5\ 1,5\ 2,3\ 1,3\ 2,4\ 1,4\ 2$。

数据范围

$1 \leq n \leq 10^6$，$1 \leq A_i \leq 10^9$。