题目描述

空の列 $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$ である。

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

输入格式

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

$N$ $a_1$ $\ldots$ $a_N$

输出格式

答えを出力せよ。

题目大意

题目大意

给定空序列 $X$ 、空栈 $S$ 和一个长度为 $N$ 的序列 $A=(a_1,a_2,\cdots,a_N)$ 。

对于 $i=1,2,\cdots,N$ ，有两种操作可以选择：

• 在栈 $S$ 中插入 $a_i$ 。
• 把 $a_i$ 从 $A$ 中删除。

（以上两种二选一）

• 当 $S$ 不为空时，把 $S$ 的栈顶移动到 $X$ 的尾处。（无论进行此操作与否）

求出序列 $X$ 的最大得分：

• 若 $X$ 是不降序列，得分为 $X$ 的长度
• 否则得分为 $0$

输入格式

第一行输入正整数 $N$ 。

第二行输入 $N$ 个正整数表示 $a_i$ 。

$N\leq 50$

$\forall i \in [1,n],1\leq a_i\leq 50$

输出格式

输出最大得分。

7
1 2 3 4 1 2 3

5

10
1 1 1 1 1 1 1 1 1 1

10

提示

制約

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

Sample Explanation 1

以下のように操作をすると最終的な $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$ です。