Write a solution in c++ that is fast: An Up-Down sequence is defined as a sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. For example, the sequence \([1, 5, 3, 4]\) is an Up-Down sequence because the differences between successive numbers are \((4, -2, 1)\), which are alternatively positive and negative. Specially, a sequence with only one integer is an Up-Down sequence with length of 1.

Given a sequence of \(N\) integers, return the length of the longest Up-Down subsequence. A subsequence is obtained by deleting some number (or 0) of elements from the original sequence, leaving the remaining elements in their original order.

Input Specification
The first line of input will contain the integer \(N\) (\(1 \le N \le 2 \times 10^6\)).

The second line of input will contain \(N\) space-separated integers representing the sequence. Each integer is in the range \([0, 10^9]\).

For 50% of test cases, \(N \le 2000\).

Output Specification
Output the length of the longest Up-Down subsequence.