Longest Array Deconstruction

题意翻译

设 $a$ 是一个序列，定义 $f_a$ 表示满足 $a_i=i$ 的位置 $i$ 的数目。 给你一个长度为 $n$ 的序列 $a$，可以删除若干个数字，最大化 $f_a$ 。 $1\le n,a_i\le 2\times 10^5$。

题目描述

Mr. Chanek gives you a sequence $ a $ indexed from $ 1 $ to $ n $ . Define $ f(a) $ as the number of indices where $ a_i = i $ . You can pick an element from the current sequence and remove it, then concatenate the remaining elements together. For example, if you remove the $ 3 $ -rd element from the sequence $ [4, 2, 3, 1] $ , the resulting sequence will be $ [4, 2, 1] $ . You want to remove some elements from $ a $ in order to maximize $ f(a) $ , using zero or more operations. Find the largest possible $ f(a) $ .

输入输出格式

输入格式

The first line contains one integer $ n $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ ) — the initial length of the sequence. The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq 2 \cdot 10^5 $ ) — the initial sequence $ a $ .

输出格式

Output an integer denoting the largest $ f(a) $ that can be obtained by doing zero or more operations.

输入输出样例

输入样例 #1

7
2 1 4 2 5 3 7

输出样例 #1

3

输入样例 #2

4
4 2 3 1

输出样例 #2

2

说明

In the first example, $ f(A) = 3 $ by doing the following operations. $ [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] $ In the second example, $ f(A) = 2 $ and no additional operation is needed.