Inversion Pairs 2

Problem Description

You are given $n$ numbers $a_1, a_2, \dots, a_n$. For two numbers $x, y$ in the array, if $x$ appears before $y$ and $x > y$, then $(x, y)$ is called an inversion pair of the array $a$. How many inversion pairs are there 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

Output one number on a single line, 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.