Longest Zigzag Subsequence

Given a sequence of integers, your task is to determine the length of the longest zigzag subsequence. A zigzag subsequence is defined as a subsequence where the differences between consecutive numbers strictly alternate between positive and negative. Formally, if the subsequence is (a_1, a_2, \dots, a_k), then for every index (i) with (2 \le i < k) either (a_i - a_{i-1} > 0) and (a_{i+1} - a_i < 0), or (a_i - a_{i-1} < 0) and (a_{i+1} - a_i > 0). Note that when consecutive numbers are equal they do not contribute to the zigzag pattern. Input is read from standard input and output is written to standard output.

inputFormat

The first line of input contains a single integer (n), which denotes the number of elements in the sequence. The second line contains (n) space-separated integers representing the sequence.

outputFormat

Output a single integer representing the length of the longest zigzag subsequence in the given sequence.## sample

5
1 7 4 9 2

5