P1698 [USACO18JAN] Out of Place B

本题翻译来自于 deepseek-v3。

Farmer John 雄心勃勃，计划尝试一件似乎从未顺利过的事情：他想为他的整个牛群拍一张照片。 为了让照片看起来更美观，他希望奶牛们从矮到高排成一行。不幸的是，就在他让奶牛们按这种方式排好队后，总是捣乱的 Bessie 走出了队伍，并重新插入到队伍中的某个位置！ Farmer John 希望通过交换奶牛对的方式让整个牛群重新排好队。请帮助他确定为了实现这一目标，他需要进行的最少交换次数。

输入的第一行包含 $N$（$2 \leq N \leq 100$）。接下来的 $N$ 行描述了 Bessie 捣乱后奶牛们的身高。每头奶牛的身高是一个范围在 $1 \ldots 1,000,000$ 的整数。奶牛的身高可能相同。

请输出 Farmer John 需要交换奶牛对的最少次数，以实现正确的排序。交换不一定需要涉及相邻的奶牛。

在这个例子中，Bessie 显然是身高为 $3$ 的奶牛。Farmer John 通过以下三次交换将奶牛们重新排序： 2 4 7 7 9 3 - 原始队伍 2 4 7 7 3 9 - 交换最后两头奶牛 2 4 3 7 7 9 - 交换第一个 $7$ 和 $3$ 2 3 4 7 7 9 - 交换 $4$ 和 $3$