当前没有测试数据。

题目描述

给出一个长度为 $n$ 的数列 $a_1,a_2...a_n$，其中 $a_i$ 的值只可能是 $1,2,4$ 中的一个。请你找出一个最小的整数 $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 4 2 2 2

3

4
1 2 4 1

-1

3
1 1 1

1

样例1解释

$a_1·a_2·a_3=a_4·a_5·a_6$，因此存在一个最小的 $k=3$。

数据范围与约束

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

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