問題文

Tさんは，諸行無常をモットーにいろいろなことに挑戦しています． Tさんはあるコンテストに長期的に参加していますが，そのコンテストにはレーティング機能があり，一度参加する毎にレーティングが変動します．それらの変動はグラフにまとめられています．

今，Tさんは彼のレーティング変動がプロットされたグラフを眺めています．彼はふと，グラフから一部の点を取り除いてそれらを結び，常に上下に変動しているような折れ線グラフ，名付けて「常ならずグラフ」を作りたくなりました． さらに，グラフに含まれる点の数が最も多いものに興味があります．

さて，あなたはTさんのために，彼のレーティング変動がプロットされたグラフから作ることのできる「常ならずグラフ」の中での最大の点の数を求めてあげることにしました．

あなたには，Tさんのあるコンテスト参加後でのレーティングが，$N$ 個，時系列で与えられます．その中からいくつかの点を取り除き「常ならずグラフ」を作るとき，ありうる点の最大数を求めなさい．常ならずグラフが作れないときは $0$ を出力しなさい．

あるグラフ $X=\\{x_1,x_2,x_3,..x_n\\}$ が「常ならずグラフ」であるとは， $|X|$ が $3$ 以上かつ， $x_1＜x_2＞x_3＜x_4＞...$ もしくは $x_1＞x_2＜x_3＞x_4<...$が成り立つことを意味します． つまり，含まれる頂点数が $3$ 未満のとき，「常ならずグラフ」ではありません．

入力

入力は以下の形式で標準入力から与えられる。

$N$ $R_1$ $R_2$ … $R_N$

• $1$ 行目には，Tさんのコンテスト参加回数を表す整数 $N (1 ≦ N ≦ 3000)$ が与えられる．
• $2$ 行目には, Tさんが $i (1 ≦ i ≦ N)$ 番目のコンテストに参加した直後のレーティング $R_i (-10^5 ≦ R_i ≦ 10^5)$ が空白切りで与えられる．

出力

与えられたグラフからいくつかの点を取り除き「常ならずグラフ」を作るとき，ありうる点の最大数を求め，$1$ 行に出力しなさい．末尾の改行を忘れないこと．

入力例1

4
1 2 5 1

出力例1

3

入力例2

5
1 2 3 4 5

出力例2

0