Longest Zigzag Subsequence

You are given an array of integers. Your task is to find the length of the longest contiguous subsequence which forms a zigzag sequence.

A sequence is said to be a zigzag sequence if the differences between successive numbers strictly alternate between positive and negative. Mathematically, for a subsequence a₁, a₂, ..., a_k (with k ≥ 1), it is a zigzag sequence if either

(a₂ - a₁) > 0, (a₃ - a₂) < 0, (a₄ - a₃) > 0, ...

or

(a₂ - a₁) < 0, (a₃ - a₂) > 0, (a₄ - a₃) < 0, ...

Note that a subsequence of length 1 is trivially a zigzag sequence.

For example:

• For the sequence [1, 7, 4, 9, 2, 5], the longest zigzag subsequence is the entire array, with length 6.
• For [1, 4, 7, 2, 5], the longest zigzag subsequence has length 4.
• For [1, 2, 3, 4, 5], the longest zigzag subsequence has length 2.

Your solution should read input from standard input and produce the result to standard output.

inputFormat

The input starts with a single integer n representing the number of elements in the array. This is followed by n space-separated integers.

Example: 6\n1 7 4 9 2 5

outputFormat

Output a single integer which is the length of the longest contiguous zigzag subsequence.

Example: For the input above, the output should be 6.

## sample

6
1 7 4 9 2 5

6