← 返回题目列表

AtCoder · code_festival_final_e

E. 始终是图表

中文机器翻译题面 查看原题

問題文

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