题目描述

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.

3
1 2 3

2

5
1 3 4 2 5

4

提示

Constraints

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