Frosh Week

Interview

Time limit1sMemory limit128 MB

Summary

Given n distinct student numbers in a line, find the minimum number of adjacent swaps needed to sort them into increasing order.

Level: Medium5 of 10
Topics: Sorting, Divide and conquer, Array, Combinatorics
Solved: No attempts yet

Problem

During Frosh Week, students play various games to get to know one another and to compete against other teams. In one such game, all the frosh on a team stand in a line and must rearrange themselves according to some criterion, such as their height, their birth date, or their student number. The line may be reordered only by repeatedly swapping two adjacent students. The team that finishes fastest wins, so to win you want to minimize the number of swaps required.

Input

The first line contains one positive integer $n$ , the number of students on the team ( $1 \le n \le 1{,}000{,}000$ ). Each of the next $n$ lines contains one integer, the student number of a student on the team. No student number appears more than once.

Output

Output a single line containing the minimum number of swaps required to arrange the students in increasing order of student number.

Examples1

Example 1
Input
```
3
3
1
2
```
Expected output
```
2
```