题目描述

这天，Aki一觉醒来，发现自己穿越到了赛博三国世界，还没来得及思考，Aki就接到了神秘使者的任务：

你现在有一支由$n$个的机器人组成精锐部队，供你指挥。这$n$个机器人的进攻方式是排成一排，向需要进攻的城池发射高能量射线，摧毁敌方的军事武器，从而让敌方丧失作战能力并拿下这座城池。

这支机器人两端（最左边和最右边）有能量装置同时给每个机器人供能，但是如果某个机器人左边或者右边存在身高大于等于它的机器人挡住了能量接收，那么它就收不到这端的供能了。某个机器人只需要保证至少存在一端给它供能，即可正常工作，若某个机器人两端的能量都接收不到，那机器人就会宕机。

现在Aki要进行大点兵，在不改变机器人的位置情况下，回收掉一批机器人，使得留下来的机器人都能正常工作。为了帮助Aki尽快实现赛博世界的大一统，现在请你帮帮Aki，他最少回收掉多少机器人，才能保证留下来的机器人都能正常工作呢？

输入格式

第一行一个正整数$n$，代表机器人数量； 第二行$n$个数，空格分开，代表每个机器人的身高。

保证所有$n \le500$，机器人身高$\le10^5$。

输出格式

一个数，代表满足条件情况下，最少回收的机器人数量。

5
2 1 2 5 4

1

7
1 8 1 1 7 6 5

2

5
1 2 3 4 5

0

Hint

第一个样例，可以只回收第一个机器人。

第二个样例，回收第3个和第4个机器人，都可以使得剩下来的机器人至少有一端能量供应。

第三个样例，不需要回收机器人，所有机器人都可以从最左端的能量装置功能。