Description

Given a sequence $a_1, a_2, \dots, a_n$, if there exists $i < j$ and $a_i > a_j$, then this pair is called an inversion. The task is to count the total number of inversions in the sequence.

Input Format

The first line contains $n$, representing the length of the sequence. The following $n$ lines each contain one element of the sequence, where the $(i+1)$-th line corresponds to the $i$-th element of the sequence.

Output Format

The total number of inversions in the sequence.

4
3
2
3
2

3

Hint

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