当前没有测试数据。

G - 使用栈的最长递增子序列

得分：600 分

问题描述

有一个空的序列 $X$ 和一个空的栈 $S$。此外，给定一个长度为 $N$ 的整数序列 $A=(a_1,\ldots,a_N)$。
对于每个 $i=1,\ldots,N$，高桥可以进行以下操作之一：

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

此外，当栈 $S$ 不为空时，高桥还可以进行以下操作：

• 将栈顶的整数移到序列 $X$ 的末尾。

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

• 如果 $X$ 是非递减的，即对于所有整数 $i(1 \leq i \lt |X|)$，有 $x_i \leq x_{i+1}$，其中 $X=(x_1,\ldots,x_{|X|})$，则得分为 $|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