#8250. 「loj」花火 省选/NOI−

时间限制:1000 ms 内存限制:256 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: jxy2012

题目描述

「Hanabi, hanabi……」

一听说祭典上没有烟火,Karen 一脸沮丧。

「有的哦…… 虽然比不上大型烟花就是了。」

还好 Shinobu 早有准备,Alice、Ayaya、Karen、Shinobu、Yoko 五人又能继续愉快地玩耍啦!

「噢……!不是有放上天的烟花嘛!」Karen 兴奋地喊道。

「啊等等……」Yoko 惊呼。Karen 手持点燃引信的烟花,「嗯??」

Yoko 最希望见到的是排列优美的烟火,当然不会放过这个机会…… 不过时间似乎已经不多了。

个烟火排成一排,从左到右高度分别为 ,这些高度两两不同。

每次 Yoko 可以选择两个相邻的烟火交换,这样的交换可以进行任意多次。

每次 Yoko 还可以选择两个不相邻的烟火交换,但这样的交换至多进行一次。

你的任务是帮助 Yoko 用最少次数的交换,使这些烟火从左到右的高度递增。

输入格式

第一行包含一个正整数

第二行包含 个正整数 ,相邻整数之间用一个空格隔开。

输出格式

输出一个整数,表示最少的交换次数。

样例

样例输入

5
3 5 4 1 2

样例输出

5

数据范围与提示

对于所有数据,满足 互不相同。

Subtask # 分值
1
2
3
4
5
6
7
8
9