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

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

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

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

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

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

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

Примеры