Out of Place

题目描述

雄心勃勃的 Farmer John 计划尝试一件似乎从来不太顺利的事情：他想给整群奶牛拍一张照片。 为了让照片看起来更好，他希望奶牛们从矮到高排成一条直线。不幸的是，就在他让奶牛们这样排好队之后，总是爱捣乱的奶牛 Bessie 走出了队伍，并在队伍的某个其他位置重新插入了自己！ Farmer John 想通过交换成对的奶牛，使整群奶牛再次正确地排好队。请帮助他确定，为了达到这一目标，他最少需要进行多少次两两交换。

输入格式

第一行输入包含 $N$（$2 \leq N \leq 100$）。接下来的 $N$ 行描述了在 Bessie 做出移动之后，奶牛们排队的身高。每个奶牛身高都是范围 $1 \ldots 1,000,000$ 内的整数。奶牛的身高可能相同。

输出格式

请输出 Farmer John 为了实现正确排序所需进行的两两交换的最小次数。交换不一定需要发生在相邻的奶牛之间。

6
2
4
7
7
9
3

3

提示

在这个例子中，Bessie 显然是身高为 3 的那头奶牛。FJ 按如下所述通过三次交换将奶牛恢复为有序： 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 题目作者：Brian Dean

标签: USACO|2018|Bronze

来源

USACO|2018|Bronze