Problem Statement

Once upon a time, there were only 3 bamboo stalks in kamipeipaa's garden.
Now there is a bamboo grove consisting of $N$ bamboo stalks lined up in a row. The height of the $i$-th bamboo stalk is $A_i$.

kamipeipaa is considering the following two conditions:
・The number of bamboo stalks is $M(3 \le M)$, and, where $B_i$ is the height of the $i$-th bamboo stalk, for $1 < i < M$, the values $B_{i-1}$,$B_i$,$B_{i+1}$ are all distinct and $B_i$ is the maximum or the minimum of the three.
・There are no bamboo stalks at all.
He wants to make either of these conditions hold.
He intends to achieve this by repeatedly using magic that "chooses one bamboo stalk and makes it vanish".
When 0 or more bamboo stalks are made to vanish so that the condition is satisfied, tell kamipeipaa the maximum number of bamboo stalks that can remain.

Input

$N$
$A_1$ $A_2$ ... $A_N$

The first line contains an integer $N (1 \le N \le 10^{5})$, the number of bamboo stalks.
The second line contains integers $A_i (1 \le A_i \le 10^{6})$, the height of the $i$-th bamboo stalk, separated by spaces.

Output

Output the maximum number of bamboo stalks that can remain.

Sample

3
5 1 4

3

6
4 4 4 5 1 4

4

5
1 2 3 4 5

0

2
9 3

0