Minimum Index Distance Between Person and Cake

Complete the function below. The function receives the full standard input as a single string and must return the exact standard output lines for the described problem.

Problem

Minimum Index Distance Between Person and Cake in a Ternary Array

Given a 1D array A of length n where each element is in {0,1,2}:

0 means empty

1 means person

2 means cake

Compute the minimum distance between any person (1) and any cake (2) in terms of index difference:

[ \min_{i,j} |i-j| \quad \text{where } A[i]=1, A[j]=2 ]

If there is no valid pair (the array does not contain both 1 and 2), output -1.

Input

Line 1: integer n

Line 2: n integers describing A

Output

One line: the minimum distance, or -1

Constraints

1 <= n <= 2*10^5

Sample Tests (5)

Input:

5

0 1 0 2 0

Output:

2

Input:

6

1 0 0 0 2 0

Output:

4

Input:

6

1 0 2 0 2 1

Output:

1

Input:

4

0 0 0 0

Output:

-1

Input:

3

2 0 2

Output:

-1

Example

Input

5

0 1 0 2 0

Output

2

Complete solveMinimumPersonCakeDistance. It has one parameter, String input, containing the full stdin payload. Return the stdout payload as an array of lines, without trailing newline characters.