#503. 希蒙的实验室·终

希蒙的实验室·终

题目描述

希蒙终于找到了失踪的UN小赛码促进会全体成员,n 位成员站成一排,希蒙要找其中的 n-k 位成员出列,使得剩下的 k 位成员排成神码队形。神码队形是指这样的一种队形:设 k 位成员从左到右依次编号为 1,2, … ,k,他们的身高分别为 t_1,t_2,, … ,t_k,则他们的身高满足 t1<<ti>ti+1>>tk(1ik)t_1< \cdots <t_i>t_{i+1}> … >t_k(1\le i\le k)

你的任务是,已知所有 n 位成员的身高,计算最少需要几位成员出列,可以使得剩下的成员排成神码队形。

输入格式

共二行。

第一行是一个整数 n2n100n(2\le n\le100),表示同学的总数。

第二行有 n 个整数,用空格分隔,第 i 个整数 t_i 130ti230(130\le t_i\le230)是第 i 位同学的身高(厘米)。

输出格式

一个整数,最少需要几位同学出列。

样例

输入样例:

8
186 186 150 200 160 130 197 220

输出样例:

4

数据范围与提示

对于 50% 的数据,保证有n20 n \le 20

对于全部的数据,保证有n100 n \le 100

PS:最后当小赛码发现,所有的成员都排成了神码队形后,他以迅雷不及掩耳之势,拿走了UN小赛码促进会全体成员的积分卡,留下他们在寒冷之中瑟瑟发抖。