题目描述

给出一个长度为 $n$ 的数列 $A_1,A_2...A_n$，满足 $A_i∈\{1,2,4\}$。求使得 $A_1×A_2...A_k=A_{k+1}×A_{k+2}...A_{n}$ 的最小整数 $k$。若 $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≤10$；

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