A71500. 编钟演绎
编程题
基础
知识点
题目描述
同学们在古典乐器馆见到了编钟，领略了编钟清脆明亮、悠扬动听的音质。谱曲体验更是让同学们跃跃欲试。游戏开始，屏幕上自动生成若干个音符，每个音符都用一个整数表示其音调高低，同学们可以选择保留或舍弃这个音符，最终按音符原有顺序形成自己的曲谱。
峰谷交错的曲谱被认为是优美的，计算机会自动合成编钟的音质并播放出来。不满足峰谷交错的曲谱会被系统拒绝。所谓峰谷交错，即除了首尾的音符外，其他所有的音符的音调要么 同时比左右两个音低，要么同时比左右两个音高。如下图所示的曲谱计算机就不会认定为优秀，系统将拒绝播放。
面对屏幕上给出的 n 个音符，计算优美乐谱的最大长度。
输入格式
第一行，包含一个正整数 n，表示生成的音符个数。
第二行，包含 n 个整数，依次表示每个音符的强度 hi。
输出格式
一行，包含一个数，表示优美乐谱的最大长度。
输入输出样例
输入 #1
5 5 3 2 1 2
输出 #1
3
说明/提示
【样例解释】
5 1 2；3 1 2；2 1 2 都是优美乐谱，最大长度为 3。
【数据范围】
对于 20 %的数据，n ≤ 10；
对于 30 %的数据，n ≤ 25；
对于 70%的数据，n ≤ 1 000，0 ≤ hi≤ 1 000；
对于 100%的数据，1 ≤ n ≤ 100 000，0 ≤ hi≤ 1 000 000，所有的 hi 随机生成，所有随机数服从某区间内的均匀分布