P6564 [POI 2007] Block Stacking KLO

PinkRabbit got a tall tower made of $n$ stacked blocks from his npy, and each block has a number written on it. Let the number on the $i$-th block from bottom to top be $a_i$. We directly denote a tower whose numbers are $a_1, a_2, \dots, a_n$ by $\{a_1, a_2, \dots, a_n\}$. PinkRabbit defines the value of a tower $\{a_1, a_2, \dots, a_m\}$ as $\sum_{i=1}^m [a_i = i]$. PinkRabbit can delete any number of blocks from the current tower. The remaining blocks will fall under gravity until they cannot fall anymore. For example, if we delete the second block from bottom to top in the tower $\{1,1,2,4,5\}$, we get the tower $\{1,2,4,5\}$, and the value of the new tower is $2$. PinkRabbit wants to delete any number of blocks from the current tower so that the value of the final tower is maximized. Since he always wins, he asks you to answer this question.

The first line contains a positive integer $n$, indicating the initial height of the tower. The second line contains $n$ positive integers $a_1, a_2, \dots, a_n$, where $a_i$ is the number on the $i$-th block from bottom to top in the initial state.

Output one integer in one line, indicating the maximum value that can be obtained.

**Explanation of Sample 1** In the initial state $\{1,1,2,5,4\}$, only $a_1$ satisfies $a_i = i$, so the total value is $1$. Delete the second block from bottom to top, and we get $\{1,2,5,4\}$. Then $a_1, a_2, a_4$ all satisfy $a_i = i$, so the total value is $3$. It is easy to prove that there is no better plan. **Constraints** For $100\%$ of the testdata, $1 \le n \le 10^5$, $1 \le a_i \le 10^6$。 Translated by ChatGPT 5