AT_code_festival_final_e 常ならずグラフ

T さん以“诸行无常”为座右铭，勇于挑战各种事情。T さん长期参加某个竞赛，该竞赛有评分（rating）功能，每次参加后评分都会发生变化。这些变化被汇总成了一张图表。 现在，T さん正在观察他的评分变化被绘制出来的图表。他突然想到，可以从图表中去除部分点，并将剩下的点连接起来，形成一条始终上下波动的折线图，他将其命名为“常ならずグラフ”。此外，他对包含点数最多的这种图表感兴趣。 现在，请你帮 T さん计算，从他的评分变化图表中可以构造出的“常ならずグラフ”所包含的最大点数。 你将得到 T さん某次竞赛后评分的时序数据，共 $N$ 个。请从中去除若干点，构造“常ならずグラフ”时，求可能包含的最大点数。如果无法构造“常ならずグラフ”，请输出 $0$。 一个图 $X=\{x_1,x_2,x_3,\ldots,x_n\}$ 被称为“常ならずグラフ”，当且仅当 $|X| \geq 3$ 且满足 $x_1 < x_2 > x_3 < x_4 > \ldots$ 或 $x_1 > x_2 < x_3 > x_4 < \ldots$。 也就是说，包含的顶点数少于 $3$ 时，不是“常ならずグラフ”。

输入通过标准输入给出，格式如下： > $N$ > $R_1\ R_2\ \ldots\ R_N$ - 第 $1$ 行为整数 $N$，表示 T さん参加竞赛的次数，$1 \leq N \leq 3000$。 - 第 $2$ 行为 $N$ 个整数 $R_i$，表示 T さん第 $i$ 次竞赛后获得的评分，$-10^5 \leq R_i \leq 10^5$，以空格分隔。

请输出从给定图表中去除若干点后，构造出的“常ならずグラフ”所能包含的最大点数。若无法构造“常ならずグラフ”，请输出 $0$。输出需换行。

由 ChatGPT 4.1 翻译