Description

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

Input Format

The first line contains $n$, the length of the sequence. The following $n$ lines contain the elements of the sequence, where the $(i+1)$-th line represents the $i$-th element of the sequence.

Output Format

The total number of inversions in the sequence.

4
3
2
3
2

3

译文

CodesOnline