题目描述

有一类只有输入语句与输出语句的程序，我们用一个非负整数序列 $[a_1, a_2, \ldots]$ 描述它。

该程序将从前往后依次执行，对于第 $i$ 个元素 $a_i$：

• 若 $a_i = 0$，表示一条输入语句：
  • 程序将从输入中读取一个整数。
• 否则，表示一条输出语句：
  • 程序将输出第 $a_i$ 次输入读取到的整数。
  • 对于给出的程序，保证执行本语句前，程序至少进行了 $a_i$ 次输入。对于你编写的程序，你同样需要保证这一点。

特别地，一个长度为 $0$ 的空程序也是合法的。

给定一个长度为 $n$ 的程序 $[b_1, \ldots, b_n]$，你需要求出能够实现相同的功能的程序所需的最短长度。

两个程序能实现相同功能，当且仅当对于任意的长度为 $10^{10^{10}}$、值为 $[1, 10^{10^{10}}]$ 之内整数的输入，两个程序执行的输出语句次数相同，且每一次输出的结果均一致。

输入格式

第一行，一个正整数 $n$，表示程序的长度。

第二行，$n$ 个非负整数 $b_1, \ldots, b_n$，描述了一个程序。

输出格式

仅一行一个整数，表示要实现相同功能的程序所需要的最小长度。

样例

5
0 0 0 1 2

4

样例 1 解释

长度为 $4$ 的程序 $[0,0,1,2]$，$[0,1,0,2]$ 均可以实现相同的功能。可以证明不存在长度 $\leq 3$ 且实现了相同功能的程序，所以答案为 $4$。

• 对于输入 $[2, 3, 4, \ldots]$，程序 $[0, 0, 0, 1, 2]$ 和 $[0, 0, 1, 2]$ 和 $[0, 1, 0, 2]$ 的输出均为 $[2, 3]$，符合题意。
• 可以验证，对于任意的长度为 $10^{10^{10}}$、值为 $[1, 10^{10^{10}}]$ 之内整数的输入，两个程序执行的输出语句次数相同，且每一次输出的结果均一致。

但是，程序 $[0,1,1]$ 无法实现相同的功能，因为对于输入 $[2, 3, 4, \ldots]$，该程序的输出为 $[2, 2]$，与原程序的 $[2, 3]$ 不相同，故不能实现相同功能。

程序 $[0,1,2]$ 是不合法的程序，因为运行第 $3$ 条指令（即一条输出语句 $a_i = 2$）时，只执行了 $1$ 次输入语句。

7
0 0 1 0 3 1 3

7

样例 2 解释

不存在更短的程序能实现相同功能。

7
0 1 0 0 2 1 0

5

样例 3 解释

长度为 $5$ 的程序 $[0,1,0,2,1]$ 可以实现相同功能。

4
0 0 0 0

0

样例 4 解释

由于没有输出语句，因此长度为 $0$ 的空程序即可实现相同功能。

数据范围

对于 $50\%$ 的数据，保证 $b_1, \ldots, b_n$ 非严格单调递增，即对于任意 $2 \le i \le n$ 均有 $b_{i-1} \le b_i$。

对于 $100\%$ 的数据，$1 \le n \le 10^5$，$0 \le b_i \le n$，且保证执行任何输出语句 $b_i$ 前，程序至少进行了 $b_i$ 次输入。