← 返回题目列表

Codeforces · 1575/L

L. 最长数组解构

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

Chanek 先生为您提供了一个序列 $$$a$$$,索引从 $$$1$$$ 到 $$$n$$$。将 $$$f(a)$$$ 定义为索引数量,其中 $$$a_i = i$$$。

您可以从当前序列中选取一个元素并将其删除,然后将剩余的元素连接在一起。例如,如果从序列 $$$[4, 2, 3, 1]$$$ 中删除 $$$3$$$-rd 元素,则生成的序列将为 $$$[4, 2, 1]$$$。

您想要使用零个或多个操作从 $$$a$$$ 中删除一些元素,以便最大化 $$$f(a)$$$。找到最大可能的$$$f(a)$$$。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 序列的初始长度。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 2 \cdot 10^5$$$) — 初始序列 $$$a$$$。

输出

输出一个整数,表示通过零次或多次运算可以获得的最大$$$f(a)$$$。

示例

输入 #1

7
2 1 4 2 5 3 7

输出 #1

3

输入 #2

4
4 2 3 1

输出 #2

2

注意

在第一个示例中,通过执行以下操作,$$$f(A) = 3$$$。

$$$[2,1,\textbf{4},2,5,3,7] \rightarrow [\textbf{2},1,2,5,3,7] \rightarrow [1,2,5,3,\textbf{7}] \rightarrow [1,2,\textbf{5},3] \rightarrow [1,2,3]$$$

在第二个示例中,$$$f(A) = 2$$$ 并且不需要额外的操作。