Frosh Week

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.

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 a single line containing the minimum number of swaps required to arrange the students in increasing order of student number.