P15705 [2018 KAIST RUN Spring] Zigzag

如果一个序列中**不存在**连续三个元素是单调的，则称该序列为“Zigzag”序列。 更正式地说，长度为 $N$ 的序列 $A$ 是 Zigzag 序列，当且仅当对于所有 $i$（$1 \leq i \leq N - 2$），既不满足 $A_i \leq A_{i+1} \leq A_{i+2}$，也不满足 $A_i \geq A_{i+1} \geq A_{i+2}$。 给定一个长度为 $N$ 的序列 $A$，你需要找出 $A$ 的一个最长子段，该子段本身是一个 Zigzag 序列。长度为 $M$ 的序列 $B$ 是长度为 $N$ 的序列 $A$ 的子段，当且仅当存在某个 $i$，使得 $B_1 = A_i$, $B_2 = A_{i+1} \cdots$, $B_M = A_{i+M-1}$ 成立。

输入包含两行。 第一行包含一个整数 $N$，表示序列 $A$ 的长度。 第二行包含 $N$ 个由空格分隔的整数。第 $i$ 个数是 $A_i$。

输出 $A$ 中最长的 Zigzag 子段的长度。

### 数据范围 - $3 \leq N \leq 5,000$ - $1 \leq A_i \leq 10^9$ ($1 \leq i \leq N$) 翻译由 DeepSeek V3.2 完成