Counting Inversions

Problem Background

Special for beginners, ^_^

Problem Description

Given a sequence $a_1, a_2, \dots, a_n$, if there exist $i < j$ and $a_i > a_j$, we call it an inversion pair. Find the number of inversion pairs in $a$.

Input Format

The first line is $n$, the length of the sequence. The next $n$ lines follow, where line $i + 1$ gives the $i$-th number in the sequence.

Output Format

The number of inversion pairs in $a$.

Sample Input

4
3
2
3
2

Sample Output

3

Constraints

1s, 1024KiB for each test case.

$N \le 10^5$, $A_i \le 10^5$.