Zigzag Sequence

A sequence is a zigzag sequence if nowhere in it do three consecutive terms increase monotonically, and nowhere do three consecutive terms decrease monotonically.

More precisely, a sequence $A$ of length $N$ is a zigzag sequence if for every $i$ with $1 \le i \le N-2$, neither $A_i \le A_{i+1} \le A_{i+2}$ nor $A_i \ge A_{i+1} \ge A_{i+2}$ holds.

A sequence $A$ of length $N$ is given. Find the maximum length of a contiguous subsequence of $A$ that is a zigzag sequence.

A sequence $B$ of length $M$ is a contiguous subsequence of the sequence $A$ of length $N$ when some $i$ exists with $B_1 = A_i$, $B_2 = A_{i+1}$, ..., $B_M = A_{i+M-1}$.

The input consists of two lines. The first line contains the length $N$ of the sequence.

The second line contains $N$ integers separated by spaces. The $i$-th number is $A_i$.

Print the maximum length of a contiguous subsequence of $A$ that is a zigzag sequence.

• $3 \le N \le 5000$
• $1 \le A_i \le 10^9$ ($1 \le i \le N$)