说明

如果一个序列中不存在连续三个元素是单调的，则称该序列为“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
1 2 3

2

5
1 3 4 2 5

4

提示

数据范围

• $3 \leq N \leq 5,000$
• $1 \leq A_i \leq 10^9$ ($1 \leq i \leq N$)

翻译由 DeepSeek V3.2 完成