Description

小 $A$ 和 小 $B$ 最近玩了一个数列游戏，游戏里面会用到一个知识叫“逆序对”，意思就是给定一串序列，如果序列中某一数对（$a_i,a_j$）满足 $a_i>a_j$ 且 $i<j$，那这样的数对叫逆序对。游戏的规则就是让你找出这个序列中逆序对的数目。

Input Format

第一行，一个数 $n$，表示序列中有 $n$ 个数。

第二行 $n$ 个数，表示给定的序列。序列中每个数字不超过 $10^9$。

Output Format

输出序列中逆序对的数目。

6
5 4 2 6 3 1

11

Hint

提示

对于 $25\%$ 的数据，$n \leq 2500$

对于 $50\%$ 的数据，$n \leq 4 \times 10^4$。

对于所有数据，$n \leq 5 \times 10^5$