题目描述

给出一个长度为 $n$ 的数列 $a_1,a_2...a_n$，满足 $a_i∈\{1,2\}$。求使得 $a_1·a_2...a_k=a_{k+1}·a_{k+2}...a_{n}$ 的最小整数 $k$。若 $k$ 不存在，则输出 $-1$。

注：$a_i∈\{1,2\}$ 的含义是：$a_i$ 的取值只可能是 $1,2$ 中的某个值。

输入格式

第一行：一个整数 $n$，表示数列长度。

第二行：$n$个整数 $a_1,a_2...a_n$，分别表示数列中的每个元素。

输出格式

一个整数，表示答案。

样例

6
1 2 1 1 2 1

2

4
1 1 2 1

-1

3
1 1 1

1

样例1解释

$a_1·a_2=a_3·a_4·a_5·a_6$，因此存在一个最小的 $k=2$ 满足条件。

数据范围与约束

对于 $30\%$ 的数据，$1≤n≤30$；

对于 $100\%$ 的数据，$1≤n≤10^5$。