炼金术士 Jeyeon 得到了一块贤者之石，它可以将一种或多种材料转化为一种不同类型的单一材料。现在，他正试图获得宇宙中最有价值的材料。世界上的每种材料都有一个对应于某个非负整数的价值，且两种材料类型不同，当且仅当它们的价值不同。

贤者之石可以消耗 $k$ ($k \ge 1$) 种材料，第 $i$ 种材料的价值为 $x_i$，并生成一种在被消耗的材料中不存在的材料。在所有此类材料中，贤者之石会生成价值最小的那种，也就是原始价值集合的 $mex$。允许消耗多个相同价值的材料。

Jeyeon 最初拥有一些价值从 $0$ 到 $N-1$ 的元素。具体来说，他拥有 $c_i$ 个价值为 $i$ 的材料。他将使用贤者之石零次或多次。最终，Jeyeon 希望只拥有一种材料。Jeyeon 想要最大化这种单一材料的价值。你能为他计算出这个值吗？注意，该材料的价值可能大于或等于 $N$。

输入格式

第一行包含一个整数 $N$。($1 \le N \le 100\,000$)

下一行包含 $N$ 个空格分隔的整数 $c_0, c_1, \dots, c_{N-1}$。($0 \le c_i \le 10^9$, $c_0 + c_1 + \dots + c_{N-1} \ge 1$)

输出格式

输出最终剩下的单一材料可能的最大价值。

样例

样例输入 1

1
1

样例输出 1

1

样例输入 2

2
0 1

样例输出 2

1

样例输入 3

6
1 0 0 0 0 1

样例输出 3

2

样例输入 4

5
0 0 0 0 1

样例输出 4

4

样例输入 5

5
1 0 1 0 1

样例输出 5

3