带栈的 LIS

题目描述

有一个空序列 $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 \le i \lt |X|)$，设 $X=(x_1,\ldots,x_{|X|})$，满足 $x_i \le x_{i+1}$，则得分为 $|X|$（其中 $|X|$ 表示 $X$ 的元素个数）。

如果 $X$ 不是非递减的，则得分为 $0$。

求可能达到的最大得分。

输入格式

输入按以下格式从标准输入给出：

$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

数据范围

• $1 \le N \le 50$
• $1 \le a_i \le 50$
• 输入均为整数