同学们在古典乐器馆见到了编钟，领略了编钟清脆明亮、悠扬动听的音质。谱曲体验更 是让同学们跃跃欲试。游戏开始，屏幕上自动生成若干个音符，每个音符都用一个整数表示 其音调高低，同学们可以选择保留或舍弃这个音符，最终按音符原有顺序形成自己的曲谱。 峰谷交错的曲谱被认为是优美的，计算机会自动合成编钟的音质并播放出来。不满足峰谷交 错的曲谱会被系统拒绝。所谓峰谷交错，即除了首尾的音符外，其他所有的音符的音调要么 同时比左右相邻的两个音低，要么同时比左右相邻的两个音高。如下图所示的曲谱计算机就不会认定为优 秀，系统将拒绝播放。

面对屏幕上给出的 n 个音符，计算优美乐谱的最大长度。

第一行一个整数n，表示接下来的音调数
第二行n个整数，表示每个音符的音调强度hi

一行，包含一个数，表示优美乐谱的最大长度

样例一说明：
5 3 2 1 2
其中5 1 2， 3 1 2， 2 1 2都是优美乐谱，最大长度为3


对于20%的数据，n <= 10
对于30%的数据，n <= 25
对于70%的数据，n <= 1000, 0<= hi <= 1000
对于100%的数据，1 <= n <= 1000000, 0<= hi <= 1000000, 所有的hi随机生成，所有的随机数服从某区间内的均匀分布

算法 枚举 暴力 动态规划 信息未来 2021