曹文信息在线OJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

5758: 滑翔翼

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：68 Solved：0
SubmitSubmit RecordStatisticsWeb BoardShowOff!

Description

J是个冒险家，他非常喜欢玩滑翔翼，一天晚上他打算偷偷地到城市里进行一次冒险。城市中有N幢建筑排成一条线，每幢建筑的高度各不相同。初始时，他可以到任何一幢建筑的顶端。他可以选择一个方向滑翔，途中可以少量地修正方向绕开一些高的建筑，但是不能掉头飞行，因为他不想在同一片街区上空飞过两次。滑翔翼没有动力装置，他只能往下滑行（即：只能从较高的建筑滑翔到较低的建筑）。在滑行过程中，他希望尽可能多地在不同建筑的顶部踩上一脚，留下自己的足迹。请问，他最多可以踩过多少幢不同建筑的顶部（包含初始时的建筑）？

Input

第一行是一个整数N(N <＝ 5000)，代表有N幢建筑。第二行包含N个不同的整数，每一个对应一幢建筑的高度h（0 < h <＝30000），按照建筑的排列顺序给出。

Output

输出一行，一个整数，代表最多可以经过的建筑数量。

Sample Input Copy 

10
2 1 3 4 5 6 7 8 9 10

Sample Output Copy 

9

Source/Category