Безумный танец

Джокер известен своей безумностью. Именно из-за нее он использует систему счисления с основанием $a$, в которой все числа состоят из цифр от $0$ до $a - 1$. Также Джокер очень любит танцевать. Он может танцевать очень долго, поэтому он придумал для себя правило, которое не даст ему танцевать бесконечно. Конечно же, правило тоже странное: когда Джокер танцует, каждую секунду, начиная с первой, он произносит вслух число секунд, прошедшее с начала танца (разумеется, он произносит это число в $a$-ичной системе счисления), без ведущих нулей. Например, если $a = 3$, первые пять чисел, которые произнесет Джокер, будут следующими:

• Спустя секунду после начала: $1$
• Спустя две секунды после начала: $2$
• Спустя три секунды после начала: $10$
• Спустя четыре секунды после начала: $11$
• Спустя пять секунд после начала: $12$

Джокер выбрал массив $b\_i$, состоящий из $a$ целых неотрицательных чисел, и решил останавливать свой танец, если после очередного произнесенного числа, он, за все время танца, ровно $b\_i$ раз произнес цифру $i$ для всех $0 \le i < a$. Помогите ему определить, сколько секунд будет длиться его танец, или же сообщите, что он будет танцевать вечно.

В первой строке дано число $a$ --- основание системы исчисления ($2 \le a \le 100\\,000$). Во второй строке дано $a$ целых чисел $b\_i$ ($0 \le b\_i \le 10^9$).

Если Джокер никогда не закончит свой танец, выведите $-1$. Иначе выведите продолжительность его танца в секундах.