如果一个序列中没有任意三个连续元素是单调的，则称该序列为 “Zigzag” 序列。

更正式地，一个长度为 $N$ 的序列 $A$ 是 Zigzag 序列，当且仅当对于所有的 $i$ ($1 \le i \le N - 2$)，既不满足 $A_i \le A_{i+1} \le A_{i+2}$，也不满足 $A_i \ge A_{i+1} \ge A_{i+2}$。

给定一个长度为 $N$ 的序列 $A$，你需要找到 $A$ 的一个最长子段，使得该子段是一个 Zigzag 序列。

长度为 $M$ 的序列 $B$ 是长度为 $N$ 的序列 $A$ 的子段，当且仅当对于某个 $i$，满足 $B_1 = A_i, B_2 = A_{i+1}, \dots, B_M = A_{i+M-1}$。

输入格式

输入包含两行。

第一行包含一个整数 $N$，表示序列 $A$ 的长度（$3 \le N \le 5\,000$）。

第二行包含空格分隔的 $N$ 个整数，其中第 $i$ 个数为 $A_i$（$1 \le A_i \le 10^9$）。

输出格式

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

样例

输入样例 1

5
1 3 4 2 5

输出样例 1

4