题目描述

小明有 $n$ 堆石子，第 $i$ 堆有 $a_i$ 颗石子，今天小明想要整理一下自己的石子堆，将所有的石子都放在第 $1$ 堆或者第 $n$ 堆。

小明可以进行如下的操作，每次选择三个数字 $i,j,k$， 满足$1 \le i < j < k \le n$， 并且保证第 $j$ 堆石子至少有 $2$ 颗石子，小明会将第 $j$ 堆中拿出 $2$ 颗石子，一颗放在第 $i$ 堆，一颗放在第 $k$ 堆。这样的操作可以进行任意多次。

现在小明想知道最少需要多少次操作可以整理好他的石子堆，如果怎么操作都无法整理好，请输出 -1。

输入格式

第一行一个数字 $T$ 表示数据组数。

对于每组数据的第一行包含一个正整数 $n$ 。

第二行包含 $n$ 个用空格隔开的正整数 $a_i$。

输出格式

$T$ 行，对于每组数据，输出最小操作次数，如果无法整理，输出 -1

样例数据

1
5
1 2 2 3 6

4

样例解释

1. 选择(i,j,k)=(1,2,5), 序列变成[2,0,2,3,7]
2. 选择(i,j,k)=(1,3,4), 序列变成[3,0,0,4,7]
3. 2次选择(i,j,k)=(1,4,5), 序列变成 [5,0,0,0,9]

数据范围

对 $20\%$ 的数据，$a_i$ 都是偶数

对 $50\%$ 的数据，$3 \le n \le 10^3$。

对 $100\%$ 的数据，$3 \le n \le 10^5, 1 \le T \le 100, 1 \le a_i \le 10^9$