P15705 [2018 KAIST RUN Spring] Zigzag

A sequence is called “Zigzag” if no three of its consecutive elements are monotone. More formally, if sequence $A$ of length $N$ is Zigzag if, for all $i$ ($1 \leq i \leq N - 2$), neither $A_i \leq A_{i+1} \leq A_{i+2}$ nor $A_i \geq A_{i+1} \geq A_{i+2}$ holds. For given sequence $A$ of length $N$, you should find a longest subsegment of $A$ which is a Zigzag sequence. Sequence $B$ of length $M$ is subsegment of sequence $A$ of length $N$ if, for some $i$, $B_1 = A_i$, $B_2 = A_{i+1} \cdots$, $B_M = A_{i+M-1}$ holds.

Input consists of two lines. The first line contains integer $N$, length of sequence $A$. The second line contains space-separated $N$ integers. $i$th number is $A_i$.

Print out the length of longest subsegment of $A$ which is a Zigzag sequence.

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