1237. 合唱队形

单点时限: 2.0 sec

内存限制: 256 MB

N 位同学站成一排,音乐老师要请其中的 (N-K) 位同学出列,使得剩下的 K 位同学排成合唱队形。

合唱队形是指这样的一种队形:设 K 位同学从左到右依次编号为 1,2…,K,他们的身高分别为 T1,T2,…,TK, 则他们的身高满足 T1<…Ti+1>…>TK(1<=i<=K)。

你的任务是,已知所有 N 位同学的身高,计算最少需要几位同学出列,可以使得剩下的同学排成合唱队形。

输入格式

第一行是一个整数 N(2<=N<=100),表示同学的总数。第一行有 n 个整数,用空格分隔,第 i 个整数 Ti(130<=Ti<=230) 是第 i 位同学的身高 (厘米)。

输出格式

输出包括一行,这一行只包含一个整数,就是最少需要几位同学出列。

样例

Input
8
186 186 150 200 160 130 197 220
Output
4

53 人解决,70 人已尝试。

62 份提交通过,共有 171 份提交。

3.9 EMB 奖励。

创建: 16 年,10 月前.

修改: 6 年,7 月前.

最后提交: 1 月,2 周前.

来源: NOIP

题目标签
DP