格格不入

题目描述

怀有雄心壮志的农夫约翰计划尝试一些似乎并不靠谱的事情：他想为他的整个牛群拍照。

为了使照片看起来更好，他希望奶牛从低到高排成一队。

不幸的是，就在他以这种方式让奶牛排好队之后，奶牛贝茜（这是个麻烦制造者）走出了队列，并插入到了队列中的其他位置！

农夫约翰想要通过不断的让成对的奶牛之间互换位置，使整个牛群重新排好队。

请帮助他确定为实现这一目标而需要在成对的奶牛之间进行的最小位置交换次数。

输入格式

第一行包含整数 N，表示奶牛总数。

接下来 N 行，用来描述在贝茜重新插入到队列中之后，从前到后，队列中每头奶牛的身高。

输出格式

输出一个整数，表示最小位置交换次数。

注意，在命令奶牛之间互换位置时，两头奶牛不一定需要彼此相邻。

6
2
4
7
7
9
3

3

提示

#### 数据范围与提示 2≤N≤100,奶牛的身高范围 1∼10^6^,奶牛的身高可能相同。 #### 样例解释 在本样例中，贝茜很显然是身高为 3 的奶牛。

约翰可使用以下三个交换来使得奶牛们按照正确顺序排列：

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 - 交换身高为 3 和身高为 4 的奶牛

来源

童程童美