14369 - 小仓鼠的储粮计划
Time Limit : 1 秒
Memory Limit : 128 MB
森林里有一排坚果，第 i 个坚果重量为 w
小仓鼠希望储粮时不要太单调，因此要求：
1、第一次选中的坚果重量任意；
2、从第二个开始，每次新选的坚果重量必须与上一次形成相反趋势：
如果刚刚是变重，则下一次必须变轻；
如果刚刚是变轻，则下一次必须变重。
3、仍然只能从左往右选择。
请帮小仓鼠尽可能多收集一下坚果
Input
第一行一个整数 n 第二行 n 个整数 w(代表一排坚果)
Output
输出最大可选数量。
Examples
Input
8 1 7 4 9 2 5 1 8
Output
8
Hint
数据范围保证 1<=n<=1e4； 1<=w<=1e9;