Longest Zigzag Subsequence

A sequence of integers zigzags if the relation between adjacent elements alternates between strictly increasing and strictly decreasing. The first relation may be an increase or a decrease. A sequence with one element zigzags.

Given a sequence of integers, find the length of the longest subsequence that zigzags. A subsequence keeps the original order and deletes as many elements as you want.

For example, the sequence 1 2 3 4 2 has several zigzagging subsequences of length 3: 1 3 2, 1 4 2, 2 3 2, 2 4 2, 3 4 2. None of them is longer than 3, so the answer is 3.

The first line contains the length of the sequence, $n$ ($1 \le n \le 1000000$). Each of the next $n$ lines contains one element $k$ of the sequence ($1 \le k \le 1000000$).

Print the length of the longest zigzagging subsequence on one line.