Imagine, you have an array of integers of size $N$. At each index of this array is a unique integer from 1 to $N$. You have to calculate how many pairs of indexes $(i, j)$ exists in the array such that:

$i < j$

$A[i] > A[j]$

Input

The first line contains a positive integer $N$ ($1 \le N \le 10^5$), the size of the array.

The next $N$ lines have one number each, the content of the index i in the array.

Output

Output a single number, the result of this problem.