Счастливый билетик 2

Назовём билетиком последовательность цифр длины n. Билетик A называется счастливым, если существует число k (1 ≤ k ≤ n) такое, что . Число k при этом называется границей счастья.

Ваша задача - написать программу, определяющую для заданного билетика его наименьшую границу счастья, если она существует.

Технические условия

Входные данные

Первая строка входного файла содержит число n (2 ≤ n ≤ 10⁶) - длина билетика A. Во второй строке содержаться цифры a₁, a₂, ..., a_n (0 ≤ a_i ≤ 9), разделённые пробелами.

Выходные данные

Если билетик является счастливым, выведите его наименьшую границу счастья, в противном случае выведите "-1".

Информация о задаче

Лимит времени: 1 секунда
Лимит памяти: 64 MB
Баллы за пройденный тест: 3.33333
Сложность: 16% 73/87
Автор: Владимир Ульянцев
Классификация: Длинная арифметика

Пример

Пример входных данных

Sample 1
4
3 2 1 6

Sample 2
4
1 2 3 4

Пример выходных данных

Sample 1
3

Sample 2
-1

← Следующее число

Список задач