Description

Search engines on the Internet often need to compare information. For example, they can estimate a person's interest in various types of information based on their rankings of certain items, thereby enabling personalized services. The differences between different ranking results can be evaluated using inversions. Consider a permutation $i_1, i_2, \dots, i_n$ of $1, 2, \dots, n$. If there exist indices $j$ and $k$ such that $j < k$ and $i_j > i_k$, then $(i_j, i_k)$ is called an inversion of this permutation. The total number of inversions in a permutation is called its inversion number. For example, the permutation $263451$ contains $8$ inversions: $(2,1)$, $(6,3)$, $(6,4)$, $(6,5)$, $(6,1)$, $(3,1)$, $(4,1)$, and $(5,1)$. Therefore, the inversion number of this permutation is $8$.

Clearly, among all $n!$ permutations of $1, 2, \dots, n$, the smallest inversion number is $0$, corresponding to the permutation $1, 2, \dots, n$; the largest inversion number is $\frac{n(n-1)}{2}$, corresponding to the permutation $n, (n-1), \dots, 2, 1$. The larger the inversion number, the greater the difference between the permutation and the original ordered permutation.

Given a permutation of $1, 2, \dots, n$, compute its inversion number.

Input Format

The first line contains an integer $n$, indicating that the permutation consists of $n$ numbers ($n \leq 100000$).
The second line contains $n$ distinct positive integers separated by spaces, representing the permutation.

Output Format

Output the inversion number of the permutation.

6
2 6 3 4 5 1

8