がっちょ君はピアノを弾こうとしている。ピアノは右側にある鍵盤ほど高い音が出る。がっちょ君はある楽譜を持っており、その楽譜に従って弾く。
楽譜には、ある時刻にどの鍵盤を弾くべきかを示す音符が時系列順に記載されている。この楽譜には和音(複数の鍵盤を押したときに出る音)は現れず、音の長さも考えないことにする。
がっちょ君はピアノを弾くとき、以下のルールに従う。
がっちょ君が使う楽譜が与えられるので、ルールに従ってその楽譜を演奏しきるには、演奏する方の腕に最小何本の指が必要かを求めよ。ただし、必要な指は6本以上になることがあることに注意せよ。
入力は以下の形式で与えられる。
N a1 a2 ... aN
1行目に、楽譜に書かれている音符の総数を表す整数Nが与えられる。
続く2行目からN+1行目までに、時刻i(1 ≤ i ≤ N)に弾くべき鍵盤が最も左の鍵盤から何番目かを表す整数aiが与えられる。
入力は以下の条件を満たす。
がっちょ君が上記ルールに従って弾くために必要な最小の指の本数を1行に出力する。
3 2 5 1
2
この場合、図1の①、② 、③ の順で鍵盤を弾く。指が2本あると、左側の指で鍵盤2を、右側の指で鍵盤5を、また左側の指で鍵盤1を弾くことができる。
5 4 5 2 1 3
3
3 4 4 4
1