B. 使它们相等

每个测试的时间限制：2 秒
内存限制：512 兆字节

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

你可以执行以下操作任意多次（可能为零次）：选择一个下标 $i$（$1 \le i \le n$）；将 $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$。

示例

输入：

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

输出：

0
-1
3