102626: [AtCoder]ABC262 G - LIS with Stack

Problem Statement

There is an empty sequence $X$ and an empty stack $S$. Also, you are given an integer sequence $A=(a_1,\ldots,a_N)$ of length $N$.
For each $i=1,\ldots,N$ in this order, Takahashi will do one of the following operations:

• Move the integer $a_i$ onto the top of $S$.
• Discard the integer $a_i$ from $A$.

Additionally, Takahashi may do the following operation whenever $S$ is not empty:

• Move the integer at the top of $S$ to the tail of $X$.

The score of the final $X$ is defined as follows.

• If $X$ is non-decreasing, i.e. if $x_i \leq x_{i+1}$ holds for all integer $i(1 \leq i \lt |X|)$, where $X=(x_1,\ldots,x_{|X|})$, then the score is $|X|$ (where $|X|$ denotes the number of terms in $X$).
• If $X$ is not non-decreasing, then the score is $0$.

Find the maximum possible score.

Constraints

• $1 \leq N \leq 50$
• $1 \leq a_i \leq 50$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

7
1 2 3 4 1 2 3

Sample Output 1

5

The following operations make the final $X$ equal $(1,1,2,3,4)$, for a score of $5$.

• Move $a_1=1$ onto the top of $S$.
• Move $1$ at the top of $S$ to the tail of $X$.
• Move $a_2=2$ onto the top of $S$.
• Discard $a_3=3$.
• Move $a_4=4$ onto the top of $S$.
• Move $a_5=1$ onto the top of $S$.
• Move $1$ at the top of $S$ to the tail of $X$.
• Move $a_6=2$ onto the top of $S$.
• Move $2$ at the top of $S$ to the tail of $X$.
• Move $a_7=3$ onto the top of $S$.
• Move $3$ at the top of $S$ to the tail of $X$.
• Move $4$ at the top of $S$ to the tail of $X$.

We cannot make the score $6$ or greater, so the maximum possible score is $5$.

Sample Input 2

10
1 1 1 1 1 1 1 1 1 1

Sample Output 2

10

问题描述

有一个空序列$X$和一个空栈$S$。此外，你还有一个长度为$N$的整数序列$A=(a_1,\ldots,a_N)$。
对于每个$i=1,\ldots,N$，按照这个顺序，Takahashi会执行以下操作之一：

• 将整数$a_i$移动到$S$的顶部。
• 从$A$中丢弃整数$a_i$。

此外，当$S$非空时，Takahashi可以执行以下操作：

• 将$S$顶部的整数移到$X$的末尾。

最终$X$的得分定义如下。

• 如果$X$是递增的，即对于所有整数$i(1 \leq i \lt |X|)$，其中$X=(x_1,\ldots,x_{|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$

输出

打印答案。

样例输入 1

7
1 2 3 4 1 2 3

样例输出 1

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$。

样例输入 2

10
1 1 1 1 1 1 1 1 1 1

样例输出 2

10