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.

Sample Input 1

4
1 5 3 4

Sample Output 1

4

Sample Input 2

10
1 7 5 10 12 15 10 5 16 8

Sample Output 2

7

Explanation

In sample case 1, the entire sequence is the longest Up-Down subsequence.

In sample case 2, one of the longest Up-Down subsequences is $[1,7,5,10,5,16,8]$ with length of 7.