406994: GYM102672 B Crazy dance

Joker is well known for his madness. That's why he uses base $$$a$$$ numeral system, where all numbers consist of digits from $$$0$$$ to $$$a - 1$$$. Also Joker likes to dance. He can dance for a very long time so he created a rule for himself which will limit his dancing. Naturally, the rule is also crazy: when Joker dance, each second, starting with the first he says aloud the number of seconds passed from the start of the dance (naturally he says the number in the $$$a$$$-based numerical system), with no leading zeros. for example, if $$$a = 3$$$, the first 5 numbers which Joker says will be:

• One second passed: $$$1$$$
• Two seconds passed: $$$2$$$
• Three seconds passed: $$$10$$$
• Four seconds passed: $$$11$$$
• Five seconds passed: $$$12$$$

Joker chose an array $$$b_i$$$, consisting of $$$a$$$ non-negative integers. He decided to stop his dance if after saying a number during entire his dancing he said digit $$$i$$$ exactly $$$b_i$$$ times for each $$$0 \le i < a$$$. Please, help him determine how many seconds his dance will last or if he will be dancing forever.

The first line has number $$$a$$$ — the base of the numerical system ($$$2 \le a \le 100\,000$$$). The second line contains $$$a$$$ integer numbers $$$b_i$$$ ($$$0 \le b_i \le 10^9$$$).

If Joker will dance forever, output $$$-1$$$. Otherwise, output the duration of dance in seconds.

10
1 2 1 1 1 1 1 1 1 1

10

2
3 5

4

5
0 0 0 0 0

-1

3
1 3 1

-1