Crazy Dance

Time limit2sMemory limit1024 MB

Summary

Given base a and target digit counts b_i, find the second at which the spoken digits first match every b_i exactly, or report -1 if it never happens.

Level: Medium6 of 10
Topics: Math, Binary search
Solved: No attempts yet

Statement

Joker is known for his madness. For that reason he uses a positional numeral system with base $a$ , in which every number consists of digits from $0$ to $a - 1$ . Joker also loves to dance. He can dance for a very long time, so he made up a rule to keep himself from dancing forever. The rule is strange too. While dancing, every second starting from the first, he says out loud the number of seconds elapsed since the dance began, written in base $a$ without leading zeros. For $a = 3$ , the first five numbers he says are $1$ , $2$ , $10$ , $11$ , and $12$ , spoken at seconds 1 through 5.

Joker chose an array $b_i$ of $a$ nonnegative integers. He decided to stop dancing as soon as, after some number he says, over the whole dance he has said digit $i$ exactly $b_i$ times for every $0 \le i < a$ . Determine how many seconds the dance lasts, or report that it goes on forever.

Input

The first line contains the base $a$ ( $2 \le a \le 100\,000$ ). The second line contains $a$ integers $b_i$ ( $0 \le b_i \le 10^9$ ).

Output

If Joker never finishes his dance, print $-1$ . Otherwise, print the duration of the dance in seconds.

Examples4

Example 1
Input
```
10
1 2 1 1 1 1 1 1 1 1
```
Expected output
```
10
```
Example 2
Input
```
2
3 5
```
Expected output
```
4
```
Example 3
Input
```
5
0 0 0 0 0
```
Expected output
```
-1
```
Example 4
Input
```
3
1 3 1
```
Expected output
```
-1
```