样例下载

题目描述

有 $N$ 个非负整数排成一排，第 $i$ 个整数为 $X_i$。

你可以进行以下操作：任意选择相邻的两个整数并分别减一。

你可以操作任意次。

你的目标是：最后得到若干个相同的非负整数。

问：你最少需要操作多少次？如果不可能完成，则输出 -1 。

多组数据。

输入格式

第一行：一个整数 $T$，表示数据组数。

对于每组数据：

• 第一行：一个整数 $N$
• 第二行：$N$ 个整数 $X_i$

数据保证所有组数据的 $\sum N ≤ 10^5$。

输出格式

共 $T$ 行，每组数据的答案占一行。

输入样例

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

输出样例

0
0
-1
4

样例解释

第 1, 2 组数据：数据本就相同，无需操作。

第 3 组数据：不可能完成。

第 4 组数据：共四次操作，以下是一种可能的操作方案：

• 第一次操作后：1 2 2 2 3 2

• 第二次操作后：1 2 2 2 2 1

• 第三次操作后：1 1 1 2 2 1

• 第四次操作后：1 1 1 1 1 1

数据范围

100% 的数据：$1 ≤ T ≤ 100$, $1 ≤ N ≤ 10^5$, $0 ≤ X_i ≤ 10^9$. 其中：

• 10% 的数据： $N ≤ 3$ , $X_i ≤ 100$。

• 20% 的数据： $N ≤ 100$ , $X_i ≤ 100$。

• 30% 的数据： $N ≤ 100$。

另外：

• 30% 的数据：所有组数据的 $N$ 均为偶数;

• 30% 的数据：所有组数据的 $N$ 均为奇数;