Longest Zigzag Subsequence

In this problem, you are given a sequence of integers and you need to determine the length of its longest zigzag subsequence. A sequence is called a zigzag sequence if the differences between consecutive terms strictly alternate between positive and negative. More formally, for a subsequence (a_1, a_2, \dots, a_k) (with (k \ge 1)), for every index (i) such that (2 \le i \le k-1), either (a_i - a_{i-1} > 0 \text{ and } a_{i+1} - a_i < 0) or (a_i - a_{i-1} < 0 \text{ and } a_{i+1} - a_i > 0).

Your task is to compute the length of the longest subsequence of the input sequence that forms a valid zigzag sequence.

inputFormat

The input is read from standard input (stdin) and consists of two lines. The first line contains a single integer (n) ( (1 \le n \le 10^5) ) representing the length of the sequence. The second line contains (n) space-separated integers representing the sequence.

outputFormat

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

6
1 7 4 9 2 5

6