Problem Description

你也喜欢玩昨日重现？

银狼真的太爱 $mex$ 了，于是又编造了一个和 mex 有关的题目。

它的第一个版本，出现在 2024 年的南京工程学院校赛，作为签到题出现，但由于歪榜，没有任何正式选手通过。

第二个版本，出现在南京工程学院 Byte 算法社周赛作为中期题出现，没有人通过。

第三个版本，出现在了"2025 年南京工程学院 Byte 算法社新生选拔赛"中作为 $D$ 题出现，对新手友好，好评如潮。

第四个版本，出现在了某外校校赛中，作为压轴题，没有人通过。

第五个版本，为了致敬武汉区域赛，银狼准备了一道与 $mex$ 有关的构造题，作为中期题，通过率不足$5\%$。

以上就是银狼与$mex$ 的前世今身，以下是这道题的第六个版本，你准备好迎接它了吗？

***

银狼拥有一个可重集，即元素可以重复出现的集合，其中数字 $i$（$0 \le i \le n$）恰好出现了 $c_i$ 次。

她可以执行任意次操作。每次操作为：从当前可重集中选取一个非空子可重集 $S$，将 $S$ 中的所有元素删除，然后将 $\operatorname{mex}(S)$ 加入可重集。

这里 $\operatorname{mex}(S)$ 表示 $S$ 中最小的未出现的非负整数。例如 $\operatorname{mex}(\{0, 1, 3\}) = 2$，$\operatorname{mex}(\{1, 2\}) = 0$。

银狼想知道，经过若干次操作后，这个可重集的 $\operatorname{mex}$ 值（即整个可重集中最小的未出现的非负整数）最大可以达到多少。

Input Format

第一行一个正整数 $n$（$1 \le n \le 2 \times 10^5$）。

第二行 $n+1$ 个整数 $c_0, c_1, ..., c_n$（$0 \le c_i \le 10^9$），保证 $\sum c_i \ge 1$。

Output Format

一行一个整数，表示答案。

3
2 2 0 0

3

2
5 5 5

5

Hint

对于第一组样例：银狼初始拥有可重集 $\{0,0,1,1\}$（$0$ 出现 $2$ 次，$1$ 出现 $2$ 次）。可以依次执行：

$\quad$ 1. 选取 $S = \{1\}$，删除 $1$ 并加入 $\operatorname{mex}(S) = 0$，可重集变为 $\{0,0,0,1\}$。

$\quad$ 2. 选取 $S = \{0, 1\}$，删除 $0, 1$ 并加入 $\operatorname{mex}(S) = 2$，可重集变为 $\{0,0,2\}$。

$\quad$ 3. 选取 $S = \{0\}$，删除 $0$ 并加入 $\operatorname{mex}(S) = 1$，可重集变为 $\{0,1,2\}$，此时 $\operatorname{mex} = 3$。

可以证明无法达到 $4$。

对于第二组样例：银狼初始拥有 $5$ 个 $0$、$5$ 个 $1$ 和 $5$ 个 $2$。通过适当的操作序列可以达到 $5$。