Responsive image

问题 D: 石头

问题 D: 石头

时间限制: 2 Sec  内存限制: 128 MB
提交: 0  解决: 28
[提交][状态][讨论版][命题人:]

题目描述

小红有n堆石头，第i堆包含ai个石头。他想让他的桌子干净，所以他决定把石头都放在第1堆或第n堆。
现在小红可以多次执行以下操作：选择1<=i<j<k<=n,从第j堆中取出两个石头(第j堆至少有两个石头)，然后放在第i堆1个,第k堆1个
现在小红想知道将所有石头移动到第1或第n堆需要的最小次数，或者说这根本不可能。

输入描述

输入包含多组样例。第一行一个整数T(0<=T<=104)--代表测试样例的组数。
接下来T组数据
每组数据第一行包含一个整数N(3<=N<=105)--代表数组的长度。
接下来是一个整数序列 a1,a2,a3,···,an(1<=ai<=109)--数组元素。
保证n在所有用例中不超过105。

输出描述

每组样例输出一个整数代表答案，如果这是不可能的输出-1。

样例输入

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

样例输出

4
-1
1
-1

提示


在第一个测试用例中，最好执行以下操作：

        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.两次选择（i，j，k）=（1，4，5）.数组变为等于[5，0，0，0，9].这个数组满足了要求，因为每块石头都被移动到堆里1和5.

操作总数为4。


[提交][状态]
ACM算法攻关部