Problem E: Frosh Week
During Frosh Week, students play various fun games to get to know each
other and compete against other teams. In one such game, all the frosh
on a team stand in a line, and are then asked to arrange themselves
according to some criterion, such as their height, their birth date,
or their student number. This rearrangement of the line must be
accomplished only by successively swapping pairs of consecutive students.
The team that finishes fastest wins. Thus, in order to win,
you would like to minimize
the number of swaps required.
Input Specification
The first line of input contains one positive integer n, the number of students
on the team, which will be no more than one million. The following n lines
each contain one integer, the student number of each student on the team.
No student number will appear more than once.
Sample Input
3
3
1
2
Output Specification
Output a line containing the minimum number of swaps
required to arrange the students in increasing order by student number.
Output for Sample Input
2
Ondřej Lhoták
This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.