问题 1375. -- 勤奋的杨老师

1375: 勤奋的杨老师

时间限制: 1 Sec  内存限制: 128 MB
提交: 10  解决: 2
[提交][状态][讨论版]

题目描述

杨老师认为他的学习能力曲线是一个拱形。勤奋的他根据时间的先后顺序罗列了一个学习清单,共有n个知识点。但是清单中的知识并不是一定要学习的,可以在不改变先后顺序的情况下有选择的进行学习,而每一个知识点都对应一个难度值。杨老师希望,后学习的知识点的难度一定不低于前一个知识点的难度(i<jai<=aj),而可能存在一个临界点,在临界点以后,他希望后学习的知识点的难度一定不高于前一个知识点的难度(i<jai>=aj)。杨老师想尽可能多的学习知识。请问:杨老师最多可以学习多少知识?

输入

第一行:一个整数n0<n<500000

接下来一行:n个整数,第i个整数ai0<ai<500000)表示第i道题目的难度。

输出

一行一个整数,表示杨老师最多可以学习多少个知识。

 

样例输入

5
1 4 2 5 1

样例输出

4

提示

来源

[提交][状态]