同学们在古典乐器馆见到了编钟，领略了编钟清脆明亮、悠扬动听的音质。谱曲体验更是让同学们跃跃欲试。游戏开始，屏幕上自动生成若干个音符，每个音符都用一个整数表示其音调高低，同学们可以选择保留或舍弃这个音符，最终按音符原有顺序形成自己的曲谱。

峰谷交错的曲谱被认为是优美的，计算机会自动合成编钟的音质并播放出来。不满足峰谷交错的曲谱会被系统拒绝。所谓峰谷交错，即除了首尾的音符外，其他所有的音符的音调要么 同时比左右两个音低，要么同时比左右两个音高。如下图所示的曲谱计算机就不会认定为优秀，系统将拒绝播放。

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

第一行，包含一个正整数 n，表示生成的音符个数。

第二行，包含 n 个整数，依次表示每个音符的强度 hi。

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

【样例解释】

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 随机生成，所有随机数服从某区间内的均匀分布

2021南京市“信息与未来”程序设计小能手

市赛