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.
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.
If a ticket is a happy, remove it lowest limit of happiness, otherwise output "-1".