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$$$ 并且不需要额外的操作。