B. Crazy dance
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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 \lt a$$$. Please, help him determine how many seconds his dance will last or if he will be dancing forever.

Input

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$$$).

Output

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

Examples
Input
10
1 2 1 1 1 1 1 1 1 1
Output
10
Input
2
3 5
Output
4
Input
5
0 0 0 0 0
Output
-1
Input
3
1 3 1
Output
-1