Longest Zigzag Subsequence

Given an array of integers, your task is to find the length of the longest zigzag subsequence. A sequence is considered a zigzag if the differences between successive elements strictly alternate between positive and negative. In other words, if for a subsequence a1, a2, a3, …, ak, the differences (a2 - a1), (a3 - a2), … alternate in sign. Formally, if we denote two counters, $$inc$$ and $$dec$$, then when a rising edge is detected (i.e. a[i] > a[i-1]), we update $$inc = dec + 1$$; and when a falling edge is detected (i.e. a[i] < a[i-1]), we update $$dec = inc + 1$$. Consider special cases where the sequence has only one element or all elements are equal. This problem requires you to implement an efficient solution using a greedy or dynamic programming approach.

inputFormat

The input is read from standard input (stdin). The first line contains a single integer n, representing the number of elements in the array. The second line contains n space-separated integers denoting the array elements.

outputFormat

Output to standard output (stdout) a single integer representing the length of the longest zigzag subsequence.## sample

1
5

1