CF1637C Andrew and Stones

Andrew 有 $n$ 堆石子，第 $i$ 堆有 $a_i$ 个石子。他想把桌子收拾干净，于是决定把所有石子都放到第 $1$ 堆或第 $n$ 堆。 Andrew 可以进行如下操作任意次：选择 $1 \le i < j < k \le n$ 这三个下标，且第 $j$ 堆至少有 $2$ 个石子，然后从第 $j$ 堆取出 $2$ 个石子，分别放到第 $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. 选择 $(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$ 次操作。 在第二个测试用例中，无法将所有石子都移到第 $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$ 次操作。 在第四个测试用例中，无法进行任何操作，且数组不满足要求，因此答案为 $-1$。 由 ChatGPT 4.1 翻译