Description

Given a sequence $a_1, a_2, \ldots, a_n$, if there exists a pair $(i, j)$ such that $i < j$ and $a_i > a_j$, then it is called an inversion pair. The task is to count the total number of inversion pairs.

Input Format

The first line contains $n$, representing the length of the sequence. The next $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 inversion pairs.

4
3
2
3
2

3

Source

CodesOnline