P1799 Sequence

Although msh has grown up, she still likes to play little games to amuse herself. One day, she wrote a sequence of numbers on paper: $1, 1, 2, 5, 4$. Then she erased one $1$, and found that the remaining $1, 2, 4$ were all in their own positions, namely $1$ at position $1$, $2$ at position $2$, and $4$ at position $4$. She wants, after erasing some numbers, to make as many numbers as possible be in their own positions in the remaining sequence. She found this game very fun and kept playing it again and again, but she cannot determine the maximum possible count, so she asks you to compute it.

The first line contains an integer $n$, the length of the sequence. The next line contains $n$ positive integers separated by spaces; the $i$-th number is $A_i$.

Output a single integer, the maximum possible number of elements that can be in their own positions in the remaining sequence after erasing some numbers, that is, after reindexing the remaining sequence from $1$, the maximum count of positions where the value equals its index.

Constraints - For $20\%$ of the testdata, $n \leq 20$. - For $60\%$ of the testdata, $n \leq 100$. - For $100\%$ of the testdata, $n \leq 10^3$. Translated by ChatGPT 5