Count Inversions

Hard#sorting #merge-sort #divide-and-conquer· solved by 0 · time limit 2.0 s

An inversion is a pair $i < j$ with $a_i > a_j$ . Count them. $O(n^2)$ is too slow for large $n$ — count while doing merge sort.

Input

$n$ , then $n$ integers.

The number of inversions.

$1 \le n \le 2 \times 10^5$ — the answer can need 64 bits.

Input

5
2 4 1 3 5

Output

Input

5
5 4 3 2 1

Output