Longest Zigzag Sequence

Given a sequence of integers, your task is to determine the length of the longest zigzag subsequence that can be derived from it. A zigzag sequence is defined as one where the differences between successive elements strictly alternate in sign. Formally, if the consecutive differences are \(d_1, d_2, \dots, d_{n-1}\), then for all valid \(i\), either \(d_i > 0\) and \(d_{i+1} < 0\) or \(d_i 0\) must hold. Note that two consecutive equal numbers are not considered a change in direction.

For example, given the sequence: [1, 7, 4, 9, 2, 5], the entire sequence forms a zigzag sequence of length 6.

If the input sequence is empty, the answer should be 0, and if it has only one element, the zigzag sequence length is 1.

inputFormat

The first line contains a single integer \(n\) representing the number of elements in the sequence. The second line contains \(n\) space-separated integers representing the sequence. If \(n = 0\), no further numbers will be provided.

outputFormat

Output a single integer, the length of the longest zigzag subsequence that can be formed from the input sequence.

## sample

6
1 7 4 9 2 5

6

</p>