J. Jiggle Joggle
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

A sequence of numbers that strictly increases and decreases alternatingly is called a "Jiggle Joggle". In other words, the differences between successive elements in a Jiggle Joggle alternate between positive and negative. Jiggle Joggles can either increase or decrease in the first step, and sequences of length 1 are considered Jiggle Joggles.

For instance, $$$[3, 1, 11, 5, 12, 7, 14]$$$ is a Jiggle Joggle. On the contrary, $$$[1, 3, 11, 9, 15]$$$ is not a Jiggle Joggle because there are consecutive positive differences. $$$[9, 5, 7, 7, 3]$$$ is also not a Jiggle Joggle because one of the differences is $$$0$$$.

As a well-trained programmer, your mission is to find the length of the longest Jiggle Joggle hidden in a given sequence of integers. You may only remove several elements from the sequence to generate the Jiggle Joggle. Changing the relative order of the elements in the sequence is forbidden.

Input

The first line contains one integer $$$n \, (1 \leq n \leq 10^5)$$$, the length of the given sequence.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n \, (-10^9 \leq a_1, a_2, \ldots, a_n \leq 10^9)$$$, which are the elements in the sequence.

Output

Output the length of the longest Jiggle Joggle hidden in the sequence.

Examples
Input
10
3 14 5 9 13 15 10 6 16 7
Output
7
Input
5
9 6 2 2 -1
Output
2
Note

In the first example, one of the longest Jiggle Joggles in the sequence is $$$[3, 14, 5, 9, 6, 16, 7]$$$, so the answer to output is $$$7$$$.