Problem E: Piano

Problem

がっちょ君はピアノを弾こうとしている。ピアノは右側にある鍵盤ほど高い音が出る。がっちょ君はある楽譜を持っており、その楽譜に従って弾く。

楽譜には、ある時刻にどの鍵盤を弾くべきかを示す音符が時系列順に記載されている。この楽譜には和音(複数の鍵盤を押したときに出る音)は現れず、音の長さも考えないことにする。

がっちょ君はピアノを弾くとき、以下のルールに従う。

• 片手のみで弾く
• 指一本で鍵盤ひとつを弾く
• 最初の音はどの指でも弾ける
• 直前の音より高い音を弾くとき、直前の音を弾いた指よりもひとつ以上右にある指を使う
• 直前の音より低い音を弾くとき、直前の音を弾いた指よりもひとつ以上左にある指を使う
• 直前の音と同じ高さの音を弾くとき、直前の音を弾いた指と同じ指を使う

がっちょ君が使う楽譜が与えられるので、ルールに従ってその楽譜を演奏しきるには、演奏する方の腕に最小何本の指が必要かを求めよ。ただし、必要な指は6本以上になることがあることに注意せよ。

Input

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

N
a1
a2
...
aN

1行目に、楽譜に書かれている音符の総数を表す整数Nが与えられる。
続く2行目からN+1行目までに、時刻i(1 ≤ i ≤ N)に弾くべき鍵盤が最も左の鍵盤から何番目かを表す整数a_iが与えられる。

Constraints

入力は以下の条件を満たす。

• 1 ≤ N ≤ 10⁵
• 0 ≤ a_i ≤ 10⁹

Output

がっちょ君が上記ルールに従って弾くために必要な最小の指の本数を1行に出力する。

Sample Input 1

3
2
5
1

Sample Output 1

2

この場合、図1の①、② 、③ の順で鍵盤を弾く。指が2本あると、左側の指で鍵盤2を、右側の指で鍵盤5を、また左側の指で鍵盤1を弾くことができる。

図1: Sample1 の図解

Sample Input 2

5
4
5
2
1
3

Sample Output 2

3

Sample Input 3

3
4
4
4

Sample Output 3

1

Note

Link

 

---