Description

给定一个大小为 $n$ 的数列 $\{a_n\}$. 你需要求出数列的逆序数，也就是逆序对数

若两个 $[1,n]$ 中的正整数 $i,j$ 满足 $i < j,a_i > a_j$，则成有序数对 $(i,j)$ 为数列 $\{a_n\}$ 的一个逆序对。

Format

Input

第一行一个正整数 $n\,(1\leq n\leq 10^5)$.

第二行 $n$ 个正整数表示数列 $\{a_n\}\,(1\leq a_i\leq 10^9)$.

Output

仅一个数，表示数列的逆序数。

Samples

7
1 9 2 4 3 6 3

8

逆序对为 $(2,3),(2,4),(2,5),(2,6),(2,7),(4,5),(4,7),(6,7)$.

Limitation

1s, 256MiB.