Problem Statement

We define a Kadomatsu sequence and its level as follows.

・ A Kadomatsu sequence of level $X$ is a sequence consisting of $2X+1$ elements.
・ When its elements are denoted by $B_{1},B_{2},...B_{2X+1}$,
　$B_{1}$ $>$ $B_{2}$ $>$ ... $B_{X}$ $>$ $B_{X+1}$ $<$ $B_{X+2}$ ... $<$ $B_{2X}$ $<$ $B_{2X+1}$ or $B_{1}$ $<$ $B_{2}$ $<$ ... $B_{X}$ $<$ $B_{X+1}$ $>$ $B_{X+2}$ ... $>$ $B_{2X}$ $>$ $B_{2X+1}$

You are given a sequence $A_{1},A_{2},...A_{N}$ consisting of $N$ elements.
Among the subsequences of this sequence that are Kadomatsu sequences, find the level of the one with the highest level.
Here, a subsequence of a sequence is the sequence obtained by choosing and deleting 0 or more elements of the sequence and arranging the remaining elements in their original order.

Input

$N$
$A_{1}\ A_{2}\ ...\ A_{N}$

$1$ $≤$ $N$ $≤$ $10^5$
$1$ $≤$ $A_{i}$ $≤$ $10^9$ $(1≤i≤N)$
All inputs are integers.

Output

Print a newline at the end.

Sample

3
1 3 2

1

1
1

0

6
5 3 1 2 4 2

2