题目描述

光头强打算从山脚到山顶修一条栈道,让游人可以拾阶而上,为了保证栈道不过于陡峭,下一步台阶不能高于当前台阶一个单位的高度，当然下一个台阶同当前台阶持平是允许的。按照位置给出地形高度，希望可以选择最多的支点修建栈道，这样栈道更为稳定。那些没有被选择的点，可以实施魔法，让其消失。求修建这样的栈道最多可以选择多少个支点?

输入格式

第一行，一个整数$N$。$N<=3000$

第二行，$N$个非负整数$(N<=1000000)$。

输出格式

一个整数，意义如题所述，修建这样的栈道最多可以选择支点数。

输入样例#1

10 
1 6 2 9 2 8 3 7 4 5

输出样例#1

6