P1698 [USACO18JAN] Out of Place B

This problem is translated from deepseek-v3.

Farmer John is ambitious and plans to try something that never seems to go smoothly: he wants to take a photo of his entire herd of cows. To make the photo look nicer, he wants the cows to stand in a line from shortest to tallest. Unfortunately, right after he lines them up this way, the troublemaking Bessie steps out of the line and reinserts herself somewhere else in the line. Farmer John wants to reorder the whole herd by swapping pairs of cows. Help him determine the minimum number of swaps he needs to achieve this goal.

The first line of input contains $N$ ($2 \leq N \leq 100$). The next $N$ lines describe the cows' heights after Bessie caused trouble. Each cow's height is an integer in the range $1 \ldots 1,000,000$. The cows' heights may be the same.

Output the minimum number of swaps Farmer John needs in order to sort the line correctly. The swaps do not necessarily have to involve adjacent cows.

In this example, Bessie is clearly the cow with height $3$. Farmer John re-sorts the cows with the following three swaps: 2 4 7 7 9 3 - original line 2 4 7 7 3 9 - swap the last two cows 2 4 3 7 7 9 - swap the first $7$ and $3$ 2 3 4 7 7 9 - swap $4$ and $3$ Translated by ChatGPT 5