Yuki 有一个长度为 $n$ 的序列 $a$。
Yuki 定义了一种操作如下：
- 选择一个长度为偶数的区间 $[l, r]$。对于满足 $l \le i \le r$ 的每个整数 $i$：
- 如果 $i - l$ 为奇数，则 $a_i$ 的值减少 $1$，即 $a_i \leftarrow a_i - 1$。
- 如果 $i - l$ 为偶数，则 $a_i$ 的值增加 $1$，即 $a_i \leftarrow a_i + 1$。
现在，Yuki 想要进行若干次操作，使得序列 $a$ 中的所有数字都相等。你需要帮助 Yuki 求出使序列 $a$ 中所有数字相等所需的最少操作次数，如果无法做到，则报告无解。
输入格式
本题包含多个测试用例。
第一行包含一个正整数 $t$ ($1 \le t \le 10^5$)，表示测试用例的数量。
对于每个测试用例：
- 第一行包含一个正整数 $n$ ($1 \le n \le 10^6$)。
- 第二行包含 $n$ 个整数 $a_1, \dots, a_n$ ($0 \le a_i \le 10^{12}$)。
保证所有测试用例中 $n$ 的总和不超过 $10^6$。
输出格式
对于每个测试用例，输出一行：
- 如果无法使所有数字相等，输出 $-1$。
- 如果可以，输出一个整数，表示使序列 $a$ 中所有数字相等所需的最少操作次数。
样例
输入样例 1
3 2 1 3 4 1 5 1 5 5 1 3 1 3 1
输出样例 1
1 2 -1
说明
对于第一个测试用例：
- 在区间 $[1, 2]$ 上执行操作。序列变为 $2, 2$，此时所有数字相等。
- 可以证明不存在操作次数更少的方案，因此答案为 $1$。
对于第二个测试用例：
- 在区间 $[1, 4]$ 上执行操作。序列变为 $2, 4, 2, 4$。
- 在区间 $[1, 4]$ 上执行操作。序列变为 $3, 3, 3, 3$，此时所有数字相等。
- 可以证明不存在操作次数更少的方案，因此答案为 $2$。
对于第三个测试用例：
- 很容易证明，无论进行多少次操作，都无法使所有数字相等，因此答案为 $-1$。