Lucky ticket 2

We call a sequence of numbers tickets of length n. A ticket is a happy, if there exists a number (1 ≤ k ≤ n) such that .The number k is called the boundary with happiness.

Your task - to write a program that determines for a given a ticket to the lowest limit of happiness, if it exists.

Input

The first line contains the number n (2 ≤ n ≤ 10^6) - the length of a ticket A. In the second row contain numbers a[1], a[2], ..., a[n] (0 ≤ a[i] ≤ 9), separated by spaces.

Output

If a ticket is a happy, remove it lowest limit of happiness, otherwise output "-1".

Examples