题目描述

One and Two

给你一个数列 $a_1, a_2, \ldots, a_n$ . 数列中的每一个数的值要么是 $1$ 要么是 $2$ . 找到一个最小的正整数 $k$，使之满足：

• $1 \leq k \leq n-1$ , and
• $a_1 \cdot a_2 \cdot \ldots \cdot a_k = a_{k+1} \cdot a_{k+2} \cdot \ldots \cdot a_n$ .

输入格式

第一行输入一个 $t$，表示测试用例数目。 每个测试用例的第一行输入一个 $n$ ( $2 \leq n \leq 1000$ ). 后面一行输入 $n$ 个整数$a_1, a_2, \ldots, a_n$ ( $1 \leq a_i \leq 2$ ).

输出格式

找不到 $k$ 输出 $-1$. 否则输出满足条件的 $k$ 的最小值。

样例 #1

样例输入 #1

3
6
2 2 1 2 1 2
3
1 2 1
4
1 1 1 1

样例输出 #1

2
-1
1

说明/提示

就是找一个最小的整数 $k$,使满足 $k$ 及其前面的乘积和其之后的乘积相等。

样例

3
6
2 2 1 2 1 2
3
1 2 1
4
1 1 1 1

2
-1
1