Description

You need to calculate how many invertion order pairs in the given array. The number invertion order pairs is the number of pair satisfing $a[i] > a[j] (i < j)$.

Format

Input

The first line contains an integer T representing the number of interger in the array.

The second line contains T numbers separated by space. You may assume that $1 \le T \le 1e6$ ，$1 \le ar[i] \le 1e19$

Output

The number of invertion order pairs in the given array.

Maybe the answer is too large, so please ouput the $answer$

Samples

5
3 4 1 2 5

4