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.