E - 常ならずグラフ

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

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_2R_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