Zigzag Sequence

Interview

Time limit1sMemory limit1024 MB

Summary

Given a sequence, find the longest contiguous block in which no three consecutive terms are monotone increasing or monotone decreasing.

Level: Medium5 of 10
Topics: Array, Two pointers, Greedy, Implementation
Solved: No attempts yet

Problem

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}$ .

Input

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$ .

Output

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

Constraints

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

Examples2

Example 1
Input
```
3
1 2 3
```
Expected output
```
2
```
Example 2
Input
```
5
1 3 4 2 5
```
Expected output
```
4
```