#YS240104. 秋游

秋游

4、秋游

秋天来了,阳光正好,不热不冷不晒,Tom和Jerry约上了它们的亲朋好友一起去海边玩耍。这天秋游一共来了n只动物,高矮不一排成了一列。Tom想找k只动物出来玩游戏,要求这k只动物形成游戏队形。

游戏队形是指这样的一种队形:假设这k只动物从左到右依次编号为1、2、3.....k,它们的身高分别为h[1],h[2],h[3],......,h[k],则它们的身高满足h[1] >......> h[i] > h[i+1] < ...... < h[k] (1 <= i <= k)。

现在已经知道这n只动物的身高,Tom需要你帮助他从这n只动物中选出k只动物,这k只动物相对顺序不变组成游戏队形,问最多可以选择多少只动物,也就是求k的最大值。

输入格式:

第一行为一个整数n(2<=n<=1000),表示动物的数量。

第二行有n个整数,用空格分隔开,第i个整数h[i](1 <= h[i] <= 1000)是第i位动物的身高。

输出格式:

一个整数,最多可以选择出多少只动物。

输入数据:
10
400 300 350 250 100 100 200 201 210 200
输出数据:
7

数据范围:

50%数据:2<=n<=4002<=n<=400

100%数据:2<=n<=10002<=n<=1000