Max Zigzag Subsequence

You are given a sequence of integers. A subsequence of this sequence is called a zigzag sequence if the differences between successive elements strictly alternate between positive and negative. In other words, for a sequence a1, a2, …, ak with k ≥ 1, it is a zigzag sequence if for every i (2 ≤ i < k) one of the following holds: [ (a_i - a_{i-1} > 0 \text{ and } a_{i+1} - a_i < 0) \quad \text{or}\quad (a_i - a_{i-1} < 0 \text{ and } a_{i+1} - a_i > 0). ] Your task is to determine the length of the longest subsequence of the given sequence that forms a zigzag sequence.

Note: A sequence with a single element is trivially a zigzag sequence (its length is 1).

inputFormat

The input is given via standard input. The first line contains a single integer (n) (the number of elements in the sequence). The second line contains (n) space-separated integers representing the sequence.

outputFormat

Output the maximum length of a zigzag subsequence, printed on a single line to standard output.## sample

6
1 7 4 9 2 5

6