How many inversions? P80595

Count the number of inversions of every given sequence of $n$ integer numbers $x_1 \dots x_n$. Remember that an inversion is a pair of indices $i$ and $j$ such that $1 \le i < j \le n$ and $x_i > x_j$.

Input

Input consists of several cases, each one with $n$ followed by the $n$ integer numbers $x_1 \dots x_n$. Assume $0 \le n \le 50000$.

Output

For every case, print the number of inversions of the sequence.