← 返回题目列表

AtCoder · abc262_g

G. 带堆栈的 LIS

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

有一个空序列 X 和一个空堆栈 S。 此外,还给你一个整数序列 A=(a_1,\ldots,a_N) 长度 N.
对于每个 i=1,\ldots,N 在此订单中,Takahashi 将执行以下操作之一:

  • 移动整数 a_i 到顶部 S.
  • 丢弃整数 a_i 来自 A.

此外,高桥可以在任何时候执行以下操作 S 不为空:

  • 移动顶部的整数 S 到尾部 X.

决赛成绩 X 定义如下。

  • If X 是非递减的,即如果 x_i \leq x_{i+1} 适用于所有整数 i(1 \leq i \lt |X|),其中 X=(x_1,\ldots,x_{|X|}),则得分为 |X| (其中 |X| 表示中的项数 X).
  • If 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.
  • 移动 1 在顶部 S 到尾部 X.
  • 移动 a_2=2 到顶部 S.
  • 丢弃 a_3=3.
  • 移动 a_4=4 到顶部 S.
  • 移动 a_5=1 到顶部 S.
  • 移动 1 在顶部 S 到尾部 X.
  • 移动 a_6=2 到顶部 S.
  • 移动 2 在顶部 S 到尾部 X.
  • 移动 a_7=3 到顶部 S.
  • 移动 3 在顶部 S 到尾部 X.
  • 移动 4 在顶部 S 到尾部 X.

我们无法得分 6 或更大,因此最大可能得分为 5.


示例输入 2

10
1 1 1 1 1 1 1 1 1 1

示例输出 2

10