Given a sequence of integers $a_1, a_2, \ldots, a_n$, find the length of the longest zigzagging subsequence in it. Sequence $s_1, s_2, \ldots, s_m$ is zigzagging if for every $1 < i < m$: $s_{i-1} < s_i > s_{i+1}$ or $s_{i-1} > s_i < s_{i+1}$.

Input

The first line of the input contains integer $n$, the length of the sequence. Next line contains $n$ integers, $a_1, a_2, \ldots, a_n$.

Output

Output the maximum length of a zigzagging subsequence in $a_1, a_2, \ldots, a_n$.

Constraints

• $1 \le n \le 10^5$
• $1 \le a_i \le 10^9$

Example

Input:

8
5 3 1 2 3 4 2 2

Output:

4

An example of a zigzagging subsequence of length 4 is 3 1 3 2.