问题描述

Monocarp 正在筹备一个团队程序设计竞赛。比赛有 $n$ 道题目，每道题要么是简单题，要么是难题，编号从 $1$ 到 $n$。

他希望第一题和最后一题都是简单题。每次操作可以任选两道题并交换它们的位置。

请计算达到目标所需的最少操作次数；如果无法做到，输出 $-1$。

输入格式

第一行输入一个整数 $t$，表示测试用例数量。

对于每个测试用例：

• 第一行输入一个整数 $n$，表示题目数量；
• 第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$。当 $a_i=0$ 时，第 $i$ 道题是简单题；当 $a_i=1$ 时，它是难题。

输出格式

对于每个测试用例，输出一行一个整数，表示最少操作次数；无法做到时输出 $-1$。

样例输入 1

4
2
0 0
2
0 1
6
1 0 0 1 0 0
5
1 0 0 1 1

样例输出 1

0
-1
1
2

样例解释 1

第一个测试用例的两端已经都是简单题，不需要操作。第二个测试用例中只有一道简单题，无法让两端同时成为简单题。

评测数据规模

对于所有数据，保证：

• $1\leq t\leq1000$；
• $2\leq n\leq50$；
• $0\leq a_i\leq1$。