Start 2023-01-12 14:00:00

USACO训练赛

End 2023-01-12 15:20:00
Contest is over.
Now 2024-03-04 23:04:31

B. 【USACO】Out of Place(不合适)(USACO 2018)

Description

农场主约翰满怀雄心壮志,他打算尝试一些似乎永远不会成功的事情:他想给他的整个牛群拍张照片。为了使照片看起来好看,他想让奶牛排成一排,从最短的到最高的。不幸的是,就在他让奶牛排成这样之后,总是惹麻烦的奶牛贝西,走出了队伍,在队伍中的其他位置重新插队!农场主约翰想换一对牛,这样整个牛群就又排好了。请帮助他确定为实现这一目标,他需要在两头奶牛之间进行交换的最小数量。

Input

输入的第一行包含N(2≤n≤100)。接下来的N行描述了贝西搬家后奶牛排成一排的高度。每头奶牛的身高都是一个整数,范围是1…1,000,000。奶牛的身高可能相同。

Output

请输出农场主约翰交换成对奶牛的最少次数,以获得正确的顺序。交换不一定需要让相邻的奶牛参与。

Examples

Input

6
2
4
7
7
9
3

Output

3

Hint

在这个例子中,贝西显然是身高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


Submit

Login

Signup
Time Limit 1 second
Memory Limit 128 MB
Submit