Out of Place#10419
Farmer John is feeling ambitious. He wants to attempt something that never seems to go quite right: taking a photograph of his entire herd of cows.
To make the photograph look nice, he asks the cows to line up in a single row from shortest to tallest. Unfortunately, right after he gets the cows lined up, Bessie the cow — always the troublemaker — steps out of line and reinserts herself at a different position in the lineup!
Farmer John now wants to swap pairs of cows so that the entire herd is once again lined up properly, from shortest to tallest. Please help him determine the minimum number of swaps needed to restore the correct order. The swapped cows do not have to be adjacent.
The first line contains one integer n~(2 \le n \le 100), the number of cows. Each of the next lines contains a single integer: the height of a cow in the current lineup, after Bessie has changed her position. Each height is an integer from to 10^6. Several cows may have the same height.
Print a single integer: the minimum number of swaps Farmer John must perform to return the lineup to sorted order.
In the following example, Bessie is clearly the cow of height . Farmer John returns the cows to sorted order using three swaps, as shown below:
2~4~7~7~9~3 — the original lineup
2~4~7~7~3~9 — swap the last two cows
2~4~3~7~7~9 — swap the first and the
2~3~4~7~7~9 — swap the and the
Example 1