Background

Original problem link: https://oier.team/problems/X4B.

Problem Description

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.

Input Format

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 Format

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

5
0 0 0 1 2

4

7
0 0 1 0 3 1 3

7

7
0 1 0 0 2 1 0

5

4
0 0 0 0

0

Hint

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