安德鲁有 $$$n$$$ 堆石头。第 $$$i$$$ 堆包含 $$$a_i$$$ 石头。他想让桌子干净,所以他决定将每块石头放在第 $$$1$$$ 堆或第 $$$n$$$ 堆上。
Andrew 可以执行以下操作任意多次:选择 $$$3$$$ 索引 $$$1 \le i < j < k \le n$$$,使得第 $$$j$$$ 堆至少包含 $$$2$$$ 石子,然后他从 $$$j$$$ 堆中取出 $$$2$$$ 石子,并将一颗石子放入 $$$i$$$ 堆中,将一颗石子放入 $$$i$$$ 堆中$$$k$$$。
告诉 Andrew 将所有石头移动到 $$$1$$$ 和 $$$n$$$ 堆中所需的最少操作次数是多少,或者确定是否不可能。
输入
输入包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10\,000$$$) - 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \leq n \leq 10^5$$$) — 数组的长度。
第二行包含整数序列 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 数组元素。
保证所有测试用例的值 $$$n$$$ 之和不超过 $$$10^5$$$。
输出
对于每个测试用例,打印将石头移动到堆 $$$1$$$ 和 $$$n$$$ 所需的最少操作数,如果不可能,则打印 $$$-1$$$。
示例
输入 #1
4 5 1 2 2 3 6 3 1 3 1 3 1 2 1 4 3 1 1 2
输出 #1
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$$$ 中。
在第二个测试用例中,不可能将所有石头放入数字为 $$$1$$$ 和 $$$3$$$ 的堆中:
1. 一开始只有一个可能的操作 $$$(i, j, k) = (1, 2, 3)$$$。该数组变为等于 $$$[2, 1, 2]$$$。
2. 现在没有可能的操作,并且数组不满足语句,所以答案是$$$-1$$$。
在第三个测试用例中,最好执行以下操作:
1. 选择 $$$(i, j, k) = (1, 2, 3)$$$。该数组变为等于 $$$[2, 0, 2]$$$。该数组满足该语句,因为每块石头都被移动到堆 $$$1$$$ 和 $$$3$$$ 中。
在第四个测试用例中,无法进行任何操作,并且数组不满足语句,因此答案为$$$-1$$$。