P11061 [MX-X4-T1] "Jason-1" IO++

Original problem link: .

There is a kind of program that contains only input statements and output statements. We describe it using a non-negative integer sequence $[a_1, a_2, \ldots]$. The program is executed from left to right. For the $i$-th element $a_i$: - If $a_i = 0$, it represents an input statement: - The program reads one integer from the input. - Otherwise, it represents an output statement: - The program outputs the integer read at the $a_i$-th input. - For the given program, it is guaranteed that before executing this statement, the program has performed at least $a_i$ inputs. For the program you write, you must also ensure this. In particular, an empty program of length $0$ is also valid. Given a program $[b_1, \ldots, b_n]$ of length $n$, you need to find the minimum length of a program that can achieve the same functionality. Two programs achieve the same functionality if and only if, for any input of length $10^{10^{10}}$ with values being integers within $[1, 10^{10^{10}}]$, the two programs execute the same number of output statements, and every output value is identical.

The first line contains a positive integer $n$, indicating the length of the program. The second line contains $n$ non-negative integers $b_1, \ldots, b_n$, describing a program.

Output a single integer in one line, indicating the minimum length of a program needed to achieve the same functionality.

**Sample Explanation #1.** The programs of length $4$, $[0,0,1,2]$ and $[0,1,0,2]$, can both achieve the same functionality. It can be proven that there is no program of length $\leq 3$ that achieves the same functionality, so the answer is $4$. - For the input $[2, 3, 4, \ldots]$, the outputs of $[0, 0, 0, 1, 2]$, $[0, 0, 1, 2]$, and $[0, 1, 0, 2]$ are all $[2, 3]$, which satisfies the requirement. - It can be verified that for any input of length $10^{10^{10}}$ with values being integers within $[1, 10^{10^{10}}]$, the two programs execute the same number of output statements, and every output value is identical. However, the program $[0,1,1]$ cannot achieve the same functionality, because for the input $[2, 3, 4, \ldots]$, its output is $[2, 2]$, which is different from the original program's $[2, 3]$, so it does not have the same functionality. The program $[0,1,2]$ is invalid, because when running the $3$-rd instruction (i.e., an output statement with $a_i = 2$), it has executed only $1$ input statement. **Sample Explanation #2.** There is no shorter program that can achieve the same functionality. **Sample Explanation #3.** A program of length $5$, $[0,1,0,2,1]$, can achieve the same functionality. **Sample Explanation #4.** Since there is no output statement, the empty program of length $0$ can achieve the same functionality. **Constraints.** For $50\%$ of the testdata, it is guaranteed that $b_1, \ldots, b_n$ is non-strictly increasing, i.e., for any $2 \le i \le n$, we have $b_{i-1} \le b_i$. For $100\%$ of the testdata, $1 \le n \le 10^5$, $0 \le b_i \le n$, and it is guaranteed that before executing any output statement $b_i$, the program has performed at least $b_i$ inputs. Translated by ChatGPT 5