Problem Description

Xiao Yang's class has a total of $N$ students, with student IDs ranging from $0$ to $N-1$.

During a certain class, the teacher arranged a handshake game for the entire class. The rules are as follows: The teacher arranged a sequence for all $N$ students to enter the classroom one by one. Each student, upon entering the classroom, needs to shake hands with the students already in the classroom whose student IDs are smaller than their own.

Now, Xiao Yang wants to know how many handshakes will occur in total for the entire class.

Hint: Consider using merge sort for descending order and solving the problem during this process.

Input Format

The input consists of 2 lines. The first line contains an integer $N$, representing the number of students. The second line contains $N$ integers separated by single spaces, describing the order in which the students enter the classroom, with each integer ranging from $0$ to $N-1$, representing the student ID.

It is guaranteed that each student will enter the classroom exactly once.

Output Format

Output a single integer on one line, representing the total number of handshakes for the entire class.

Sample Input and Output

Sample Input #1

4
2 1 3 0

Sample Output #1

2

Sample Input #2

6
0 1 2 3 4 5

Sample Output #2

15

Notes

Sample Explanation 1:

The student with ID $2$ enters the classroom, and there are no other students present.

The student with ID $1$ enters the classroom, and there is the student with ID $2$. Since the student with ID $1$ has a smaller ID than the student with ID $2$, they do not need to shake hands.

The student with ID $3$ enters the classroom, and there are students with IDs $1$ and $2$. Since the student with ID $3$ has a larger ID than both, they need to shake hands with each of the other two students.

The student with ID $0$ enters the classroom, and there are students with IDs $1$, $2$, and $3$. Since the student with ID $0$ has a smaller ID than all of them, they do not need to shake hands with any of the other students.

Sample Explanation 2:

All students in the class will shake hands with each other, because each student, upon entering the classroom, will find that their ID is the largest among those already in the classroom, so they need to shake hands with every other student in the classroom.

For $30\%$ of the test cases, it is guaranteed that $N \leq 100$.

For all test cases, it is guaranteed that $2 \leq N \leq 3 \times 10^5$.

见题面 Input 部分

见题面 Output 部分