← 返回题目列表

Codeforces · 2038/B

B. 使其相等

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

给定一个整数数组 $$$a$$$,大小为 $$$n$$$。数组的元素编号从 $$$1$$$ 到 $$$n$$$。

您可以执行以下操作任意次数(可能为零):从 $$$1$$$ 到 $$$n$$$ 选择索引 $$$i$$$;将 $$$a_i$$$ 减少 $$$2$$$ 并将 $$$a_{(i \bmod n) + 1}$$$ 增加 $$$1$$$。

执行操作后,数组的所有元素都应为非负相等整数。

您的任务是计算必须执行的最少操作数。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)。

对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 您必须执行的最少操作数。如果不可能使数组的所有元素都相等,则打印 -1。

示例

输入 #1

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

输出 #1

0
-1
3