Inversion Pairs (II)

Problem Description

Given $n$ numbers $a_1, a_2, \dots, a_n$. For two numbers $x, y$, if $x$ appears before $y$ and $x$ is greater than $y$, then $(x, y)$ is called an inversion pair of the array $a$. How many inversion pairs does array $a$ have in total? Formally, count the number of pairs $(i, j)$ such that $i < j$ and $a_i > a_j$.

Input Format

The first line contains an integer $n$.

The next line contains $n$ integers $a_1, a_2, \dots, a_n$.

Output Format

One line with one number, the answer.

Sample Input

4
4 2 3 1

Sample Output

5

Sample Explanation

The 5 inversion pairs are $(4,2)$, $(4,3)$, $(4,1)$, $(2,1)$, $(3,1)$.

Constraints

For $100\%$ of the data: $2 \leq n \leq 100000$, $1 \leq a_i \leq n$, and each number appears exactly once.