Назовём билетиком последовательность цифр длины n. Билетик A называется счастливым, если существует число k (1 ≤ k ≤ n) такое, что . Число k при этом называется границей счастья.
Ваша задача - написать программу, определяющую для заданного билетика его наименьшую границу счастья, если она существует.
Первая строка входного файла содержит число n (2 ≤ n ≤ 10^6) - длина билетика A. Во второй строке содержаться цифры a_1, a_2, ..., a_n (0 ≤ a_i ≤ 9), разделённые пробелами.
Если билетик является счастливым, выведите его наименьшую границу счастья, в противном случае выведите "-1".