配点 : $600$ 点

問題文

空の列 $X$ と空のスタック $S$ があります。また、項数が $N$ の整数列 $A=(a_1,\ldots,a_N)$ が与えられます。 高橋君は $i=1,\ldots,N$ の順に、以下の $2$ つの操作のうち一方を行います。

• $A$ の先頭の整数 $a_i$ を $S$ の先頭に移動させる。
• $A$ の先頭の整数 $a_i$ を捨てる。

また、高橋君は $S$ が空でない任意のタイミングで次の操作をすることが出来ます。

• $S$ の先頭の整数を $X$ の末尾に移動させる。

最終的な $X$ に対し、スコアを以下のように定めます。

• $X$ が広義単調増加な場合、すなわち $X=(x_1,\ldots,x_{|X|})$ とした時に任意の整数 $i(1 \leq i \lt |X|)$ に対して $x_i \leq x_{i+1}$ が成り立つ場合、スコアは $|X|$ である。($|X|$ は $X$ の項数)
• $X$ が広義単調増加でない場合、スコアは $0$ である。

スコアの最大値を求めてください。

制約

• $1 \leq N \leq 50$
• $1 \leq a_i \leq 50$
• 入力はすべて整数

入力

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

$N$

$a_1$ $\ldots$ $a_N$

出力

答えを出力せよ。

7
1 2 3 4 1 2 3

5

以下のように操作をすると最終的な $X$ が $(1,1,2,3,4)$ となり、スコアが $5$ になります。

• $a_1=1$ を $S$ の先頭に移動させる。
• $S$ の先頭の $1$ を $X$ の末尾に移動させる。
• $a_2=2$ を $S$ の先頭に移動させる。
• $a_3=3$ を捨てる。
• $a_4=4$ を $S$ の先頭に移動させる。
• $a_5=1$ を $S$ の先頭に移動させる。
• $S$ の先頭の $1$ を $X$ の末尾に移動させる。
• $a_6=2$ を $S$ の先頭に移動させる。
• $S$ の先頭の $2$ を $X$ の末尾に移動させる。
• $a_7=3$ を $S$ の先頭に移動させる。
• $S$ の先頭の $3$ を $X$ の末尾に移動させる。
• $S$ の先頭の $4$ を $X$ の末尾に移動させる。

また、スコアを $6$ 以上にすることは出来ません。よってスコアの最大値は $5$ です。

10
1 1 1 1 1 1 1 1 1 1

10