When playing a new game (some hybrid of bowling and billiards), N balls are used, numbered from 1 to N. At the beginning of the game, these balls must be laid out in a line in numerical order. During the game, their order may change.
In order to arrange the balls before the start of the next game, the following device is used. This device consists of a head, which, moving over the balls, can "suck" and "spit out" balloons. To get a better idea of this device, imagine a vacuum cleaner that can suck in balls, move to the right place, and there, blowing in the opposite direction, “spit out” the balls.
When a balloon is sucked in, all the balloons that were to the right of the sucked one are shifted to the left. "Spit out" the ball can be between any two balls (and also before the first ball or after the last one), then the spitting ball is inserted between these balls, and all the balls that are to the right of the inserted one are shifted to the right.
More than one ball can be sucked into the device at the same time, and when spitting out the ball, the last sucked ball is spit out first, then the penultimate one, and so on. (i.e. the device works on the principle of a stack). The balls are spat out one at a time, i.e. you can spit out only one ball, leaving the rest inside the device (in this case, you can continue to “spit out” the balls in the same or in another place, or suck in new balls).
The most energy-intensive of the described operations is the operation of sucking the ball, so we want to minimize the number of just such operations.
Write a program that, given the initial arrangement of the balls, will determine the minimum number of suctions required to arrange the balls in numerical order.
Input
In the input file, the number N is given first — number of balls (1≤N≤1000). Then there are N numbers that give the numbers of the balls in order from left to right in their current location (each number — from 1 to N, and each of the numbers occurs exactly once in the sequence).
Output
Output a single number — the minimum number of ball sucking operations that will be required to arrange the balls in the order of their numbers.
Comments on sample tests
1.You can suck, for example, balloon number 2 and spit it out between the 1st and 3rd balloon.
2.>You can do something like this. First,
suck balloon number 1, then – ball number 2. Then we move to the beginning and spit out the ball before the 4th ball (this will be ball number 2). Next, suck in balloon number 3 and spit it out between balloons 2 and 4. Then move to the beginning and spit out balloon number 1 there. However, this is not the only possible ordering of the balloons in this example.
| Input |
Output |
|
3
2 1 3
|
1 |
|
4
4 3 2 1
|
3 |
Team Olympiad, Moscow Team Olympiad, grades 9-11, 2007, League A, Problem F