407310: GYM102759 H Alchemy

Jeyeon the alchemist has obtained the philosopher's stone which can transform one or more materials into a single material of a different type. Now he is trying to obtain the most valuable material in the universe. Every material in the world has a value corresponding to some nonnegative integer, and two materials are different in type if and only if they differ in value.

The philosopher's stone can consume $$$k$$$ ($$$k \geq 1$$$) materials, the $$$i$$$th having value $$$x_i$$$, and generates a material that was not among the consumed values. Over all such materials, the philosopher's stone will generate the material with minimum value, also known as the mex of the original values. It is allowed to consume multiple materials of the same value.

Jeyeon starts out with some elements with values varying from $$$0$$$ to $$$N-1$$$. Specifically, he has $$$c_i$$$ materials with value $$$i$$$. He will use the philosopher's stone zero or more times. In the end, Jeyeon wants to own exactly one material. Jeyeon wants to maximize the value of this single material. Can you calculate this value for him? Note that the value of this material may be greater than or equal to $$$N$$$.

The first line contains the single integer $$$N$$$. ($$$1 \le N \le 100\,000$$$)

The next line contains $$$N$$$ space-separated integers $$$c_0, c_1, \cdots, c_{N-1}$$$. ($$$0 \le c_{i} \le 10^{9}$$$, $$$c_{0} + c_{1} + \cdots + c_{N-1} \ge 1$$$)

Print the maximum possible value of the single remaining material.

1
1

1

2
0 1

1

6
1 0 0 0 0 1

2

5
0 0 0 0 1

4

5
1 0 1 0 1

3