Longest Zigzag Subsequence

Given a sequence of integers, your task is to determine the length of the longest zigzag subsequence within the sequence. A zigzag subsequence is defined as a subsequence where the differences between consecutive elements alternate in sign. More formally, if the subsequence is \(a_1, a_2, \dots, a_k\), then for every \(i\) with \(2 \le i \le k-1\) either

\(a_i - a_{i-1} > 0\) and \(a_{i+1} - a_i < 0\), or \(a_i - a_{i-1} 0\).

Note that a sequence with one element is trivially a zigzag subsequence of length 1, and an empty sequence has a length of 0.

Your goal is to compute the maximum length of any such subsequence from the provided input.

inputFormat

The first line of input contains a single integer \(n\) indicating the number of elements in the sequence. The second line contains \(n\) integers separated by spaces, representing the sequence.

outputFormat

Output a single integer denoting the length of the longest zigzag subsequence.

6
1 7 4 9 2 5

6