409391: GYM103496 D Decorum Sensing

Alice has been adjusting to her online microbiology class really well! She has a synchronous session with her instructor every week. By far, her favorite part is at the end of the session, when everyone says, "Thank you, sir!" one after another. It gives her a small burst of well-needed wholesome energy for the week. And her teacher friends have confirmed that they really appreciate hearing it as well!

Alice noticed that some students are shier than others. There are $$$n$$$ students in her microbiology class. The $$$i$$$th student will say "Thank you, sir!" only after at least $$$A_i$$$ other students have also said "Thank you, sir!" (if $$$A_i = 0$$$, then the $$$i$$$th student says "Thank you, sir!" immediately after class ends). Alice calls this behavior decorum sensing, because these students are trying to get a feel for what is appropriate to say or do based on what everyone else is doing.

Given the values of $$$A_1, A_2, A_3, \dots, A_n$$$, find the number of students who will eventually say "Thank you, sir!"

The first line of input contains a single integer $$$n$$$.

The second line of input contains $$$n$$$ space-separated integers $$$A_1, A_2, A_3, \dots, A_n$$$.

Output a single integer, the number of students who will eventually say "Thank you, sir!"

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 0 \leq A_i \leq n \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{25} & 1 \leq n \leq 6 \\ \hline 2 & \mathbf{25} & 1 \leq n \leq 100 \\ \hline 3 & \mathbf{25} & 1 \leq n \leq 1000 \\ \hline 4 & \mathbf{25} & 1 \leq n \leq 10^5 \\ \hline \end{array}\\

\end{align*}$$$$$$

10
1 6 1 8 0 3 3 9 8 8

5

4
1 2 3 4

0

In the first sample input, we can show that the $$$1$$$st, $$$3$$$rd, $$$5$$$th, $$$6$$$th, and $$$7$$$th students all say, "Thank you, sir!"

• First, the $$$5$$$th student says, "Thank you, sir!"
• After hearing this, the $$$1$$$st and $$$3$$$rd students say, "Thank you, sir!"
• After hearing them, the $$$6$$$th and $$$7$$$th students say, "Thank you, sir!"
• No further students say anything after that.

In the second sample input, no one will say "Thank you, sir!" How sad.