题目描述

给出一个长度为 $n$ 的数列 $a_1,a_2...a_n$，其中 $a_i$ 的值为 $1$ 或 $2$。请你找出一个最小的整数 $k$，使得这个数列中的前 $k$ 个数的乘积与剩余的所有数的乘积相等，即 $a_1·a_2...a_k=a_{k+1}·a_{k+2}...a_{n}$。若 $k$ 不存在，则输出 $-1$。

输入格式

第一行：一个整数 $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$。