← 返回题目列表

Codeforces · 1637/C

C. 安德鲁和斯通斯

中文机器翻译题面 查看原题

安德鲁有 $$$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$$$。