#5299. Time

内存限制:512 MiB 时间限制:1000 ms 输入文件:time.in 输出文件:time.out
题目类型:传统 评测方式:文本比较
上传者: zhouhao

题目描述

小A现在有一个长度为n的序列{xi},但是小A认为这个序列不够优美。 小A认为一个序列是优美的,当且仅当存在k ɛ[1,n],满足: X1<=x2<=... Xk>=xK+1>=xK+1>=...>=xn 现在小A可以进行若干次操作,每次可以交换序列中相邻的两个项,现在他想知道最少操作多少次之 后能够使序列变为优美的。

输入格式

第一行一个正整数n,表示序列的长度。 接下来一行n个整数,表示初始的序列。

输出格式

输出一行一个整数,表示最少需要的操作次数。

样例

Sample Input

5
3 4 5 1 2

Sample Output

1

数据范围与提示

对于30%的数据,n<=12 对于60%的数据,n <= 100000, ai互不相同 对于100%的数据,n,ai<= 100000