Longest Zigzag Subsequence Length

You are given an array of integers. Your task is to compute the length of the longest zigzag subsequence in the array.

A zigzag subsequence is a sequence where the differences between consecutive elements strictly alternate between positive and negative. Formally, if the subsequence is denoted by \(a_1, a_2, \dots, a_k\), then for every \(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\).

If the array is empty, the answer is 0. If the array has only one element, then the answer is 1. You are required to implement an efficient solution that reads from standard input and writes to standard output.

inputFormat

The input is provided via standard input (stdin) and consists of two lines.

1. The first line contains an integer \(n\) (\(n \ge 0\)) denoting the number of elements in the array.
2. If \(n > 0\), the second line contains \(n\) space-separated integers representing the elements of the array.

If \(n = 0\), there will be no second line.

outputFormat

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

6
1 5 4 9 2 8

6