Безумный танец
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Джокер выбрал массив $$$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$$$. Иначе выведите продолжительность его танца в секундах.

Примеры

Входные данные
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