Щастливий квиточок 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".

Приклади