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)\).
Output
Output an integer denoting the largest \(f(a)\) that can be obtained by doing zero or more operations.
Note
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.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
2 1 4 2 5 3 7
|
3
|
|
2
|
4
4 2 3 1
|
2
|