405148: GYM101806 Z 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 ≤ i ≤ N - 2), neither A_i ≤ A_i + 1 ≤ A_i + 2 nor A_i ≥ A_i + 1 ≥ 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₁ = A_i, B₂ = A_i + 1 ..., B_M = A_{i + M - 1} holds.

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 A_i. (1 ≤ A_i ≤ 10⁹)

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

5
1 3 4 2 5

4