Z. Zigzag
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

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 ≤ i ≤ N - 2), neither Ai ≤ Ai + 1 ≤ Ai + 2 nor Ai ≥ Ai + 1 ≥ Ai + 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, B1 = Ai, B2 = Ai + 1 ..., BM = Ai + M - 1 holds.

Input

Input consists of two lines.

The first line contains integer N, length of sequence A. (3 ≤ N ≤ 5, 000)

The second line contains space-separated N integers. ith number is Ai. (1 ≤ Ai ≤ 109)

Output

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

Example
Input
5
1 3 4 2 5
Output
4