给定一个整数数组 $$$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