AT_abc262_g [ABC262G] LIS with Stack

题目描述

题目大意

给定空序列 $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$

输出格式

输出最大得分。

输入输出样例 #1

输入 #1

7
1 2 3 4 1 2 3

输出 #1

5

输入输出样例 #2

输入 #2

10
1 1 1 1 1 1 1 1 1 1

输出 #2

10