CF1575L Longest Array Deconstruction

Chanek 先生给你一个从 $1$ 到 $n$ 编号的序列 $a$。定义 $f(a)$ 为满足 $a_i = i$ 的下标 $i$ 的个数。 你可以从当前序列中选择一个元素并将其移除，然后将剩下的元素拼接在一起。例如，如果你从序列 $[4, 2, 3, 1]$ 中移除第 $3$ 个元素，得到的新序列为 $[4, 2, 1]$。 你希望通过移除若干个元素（可以为零），使得 $f(a)$ 最大。请你求出可以得到的最大的 $f(a)$。

第一行包含一个整数 $n$（$1 \leq n \leq 2 \times 10^5$），表示初始序列的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 2 \times 10^5$），表示初始序列 $a$。

输出一个整数，表示通过若干次操作后可以得到的最大的 $f(a)$。

在第一个样例中，通过如下操作可以得到 $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$，且无需进行任何操作。 由 ChatGPT 4.1 翻译