A. 神秘自动机

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

题目描述

小L今天想去爬上锻炼身体,并且当作放松放松,因此他选择了 n 座山峰。

其中,高度越高,看到的风景越好,并且就算在相同高度下,不同山峰的风景也不同。

因此小L想要看尽可能高和多的风景。他想要从山底爬到最高处看风景,并且看到的风景数量最多。

(小L不希望当前看到的风景比上一次的差,如果比上一次的风景差,那么当前风景不计入有效风景数中)

他有个初始的登山高度计划( A_1,A_2,A_3,......,A_n ),只有爬完当前这座山峰才继续在此高度上继续爬下一座山峰。

他希望你帮助他重新进行规划,使得小L所欣赏到的有效风景数最多。

而你每次都只能选位置相邻的两个高度进行交换。

如:1 4 2 5 6 5 ,能交换 A_4 A_5 ,变为 1 4 2 6 5 5

问你最少要交换几次。

输入格式

第一行,一个数字 n 1<=n<=5000

第二行, n 个整数 A_i ( 1<=A_i<=10^9 )

输出格式

输出在满足要求下的最少操作次数

样例

输入样例

4
3 1 2 4

输出样例

2