880082 - 公园树木

通过次数

0

提交次数

0

Time Limit : 1 秒
Memory Limit : 128 MB

某公园有N(3≤N≤50)棵树排成一排,已知每棵树的高度。现要去掉一些树,使得剩下树的高度从左至右呈现先递增再递减的规律(即剩余的树中仅有一棵最高的树,且它左侧的所有树中后一棵树都要比前一棵树高,它右侧的所有树中后一棵树都要比前一棵树矮) 给出N棵树的高度(高度单位:m,1.0≤每棵树高度≤100.0,保留一位小数),请你计算出最少去掉几棵树才能使这排树呈现先递增再递减的规律,如果不能呈现则输出-1(只有递增或者只有递减都为不能呈现)。 例如:N=10,10棵树的高度从左到右依次为1.0、2.3、1.2、1.7、1.1、2.0、1.8、1.8、1.2、1.9。 https://img-blog.csdnimg.cn/direct/35fee81e4f74417dad543e660c100223.png 要使这排树呈现先递增再递减的规律,最少去掉4棵树,去掉的编号分别为2、5、8、10。 https://img-blog.csdnimg.cn/direct/3061a4111146490da052a60540b8ea2f.png 剩余树的高度依次为1.0、1.2、1.7、2.0、1.8、1.2,最高树为2.0,其左侧树的高度依次为1.0、1.2、1.7、2.0,呈现递增趋势(从左至右且包含最高树);其右侧树的高度依次为2.0、1.8、1.2,呈现递减趋势(从左至右且包含最高树)。

Input

第一行输入一个正整数N(3≤N≤50),表示这排树的数量 第二行输入N个数(1.0≤每个数≤100.0,保留一位小数),表示每棵树的高度,每个数之间以一个空格隔开

Output

输出一个整数,表示最少去掉几棵树才能使这排树呈现先递增再递减的规律,如果不能呈现则输出-1

Examples

Input

10
1.0 2.3 1.2 1.7 1.1 2.0 1.8 1.8 1.2 1.9

Output

4

Input

13
37.7 77.7 2.7 15.6 39.9 3.8 71.0 21.8 26.7 19.7 74.2 20.2 37.5

Output

7

Input

18
2.8 4.3 5.5 7.6 2.2 4.4 6.9 2.3 2.5 7.6 2.5 6.5 3.4 1.2 2.3 5.4 2.2 3.0

Output

9