問題文
T先生以无常为座右铭,正在尝试各种事物。 T先生很长时间以来一直参加某个比赛,但该比赛有评分功能,每次参加时评分都会发生变化。这些变化总结在图表中。
T 先生当前正在查看绘制其评级波动的图表。他突然想从图中删除一些点,并将它们连接起来,创建一个不断上下波动的折线图,他称之为“不总是图”。 此外,我们对包含最多点数的图感兴趣。
现在,您决定为 T 先生找到“始终图表”中的最大点数,该图表可以从绘制他的评级波动的图表中创建。
参加某场比赛后,您获得了T先生的评分。N 片段按时间序列给出。从图中删除一些点以创建“始终图”时,找到可能的点的最大数量。当您无法始终创建图表时 输出 0 。
图表 X=\{x_1,x_2,x_3,..x_n\} “并不总是一个图”这一事实意味着 |X| 是 3 及以上,以及 x_1<x_2>x_3<x_4>... 或 这意味着 x_1>x_2<x_3>x_4<...成立。 换句话说,包含的顶点数是 当它小于 3 时,它不是“始终是一个图”。
入力
输入是按以下格式从标准输入给出的。
N R_1 R_2 … R_N
- 1 行是一个整数,代表T先生参加比赛的次数。 给出了 N (1 ≦ N ≦ 3000) 。
- 2 线路中,T先生 参加第 i (1 ≦ i ≦ N) 次比赛后立即评分 R_i (-10^5 ≦ R_i ≦ 10^5) 用空格分隔。
出力
当从给定图中删除一些点以创建“不寻常的图”时,找到可能的点的最大数量, 在1 行输出。不要忘记最后的换行符。
入力例1
4 1 2 5 1
出力例1
3
入力例2
5 1 2 3 4 5
出力例2
0