AT_code_festival_final_e 常ならずグラフ

[problemUrl]: https://atcoder.jp/contests/code-festival-2014-final/tasks/code_festival_final_e 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\

入力は以下の形式で標準入力から与えられる。 > $ 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 $ 行に出力しなさい．末尾の改行を忘れないこと．