3987: 「LibreOJ Round #6」花火
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
> 「Hanabi, hanabi……」
>
> 一听说祭典上没有烟火，Karen 一脸沮丧。
>
> 「有的哦…… 虽然比不上大型烟花就是了。」
>
> 还好 Shinobu 早有准备，Alice、Ayaya、Karen、Shinobu、Yoko 五人又能继续愉快地玩耍啦！
>
> 「噢……！不是有放上天的烟花嘛！」Karen 兴奋地喊道。
>
> 「啊等等……」Yoko 惊呼。Karen 手持点燃引信的烟花，「嗯？？」
>
> Yoko 最希望见到的是排列优美的烟火，当然不会放过这个机会…… 不过时间似乎已经不多了。
$n$ 个烟火排成一排，从左到右高度分别为 $h_1,h_2,\cdots,h_n$，这些高度两两不同。
每次 Yoko 可以选择两个相邻的烟火交换，这样的交换可以进行任意多次。
每次 Yoko 还可以选择两个不相邻的烟火交换，但这样的交换至多进行一次。
你的任务是帮助 Yoko 用最少次数的交换，使这些烟火从左到右的高度递增。
输入
第一行包含一个正整数 $n$。
第二行包含 $n$ 个正整数 $h_1,h_2,\cdots,h_n$，相邻整数之间用一个空格隔开。
输出
输出一个整数，表示最少的交换次数。
样例输入 复制
5
3 5 4 1 2样例输出 复制
5提示
数据范围：对于所有数据，满足 $1\le n\le 300,000$，$1\le h_i\le n$，$h_i$ 互不相同。 | Subtask # | 分值 | $n$ | |:-:|:-:|:-:| | 1 | $6$ | $\le 4$ | | 2 | $11$ | $\le 8$ | | 3 | $16$ | $\le 100$ | | 4 | $8$ | $\le 300$ | | 5 | $13$ | $\le 700$ | | 6 | $7$ | $\le 2,000$ | | 7 | $6$ | $\le 6,000$ | | 8 | $14$ | $\le 60,000$ | | 9 | $19$ | $\le 300,000$ |