该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

三色齿轮

题目描述

有一排 $n$ 个齿轮，从左到右编号为 $1,2,\dots,n$。

每个齿轮都有一个状态，状态为 $0,1,2$ 之一。

你可以进行若干次操作。每次操作可以选择一个整数 $i$，满足 $1\le i<n$，然后同时执行以下变化：

也就是说，一次操作会使第 $i$ 个齿轮的状态增加 $1$，第 $i+1$ 个齿轮的状态减少 $1$，所有状态都在模 $3$ 意义下变化。

你的目标是通过若干次操作，使得所有齿轮的状态完全相同。

请输出最少需要多少次操作。

如果无法做到，输出 $-1$。

输入格式

第一行输入一个整数 $t$，表示测试组数。

对于每组测试数据：

第一行输入一个整数 $n$，表示齿轮数量。

第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示每个齿轮的初始状态。

数据范围

• $1 \le t \le 10^4$
• $1 \le n \le 2 \times 10^5$
• 对于所有 $1 \le i \le n$，满足 $0 \le a_i \le 2$
• 保证所有测试数据中 $n$ 的总和不超过 $2 \times 10^5$

输出格式

对于每组测试数据，输出一个整数，表示最少操作次数。

如果无法使所有齿轮状态完全相同，输出 $-1$。

输入输出样例 #1

输入 #1

4
3
0 2 1
3
0 1 1
5
2 0 1 2 1
1
2

输出 #1

1
-1
3
0

说明/提示

对于第一组数据，初始状态为：

选择 $i=2$ 操作一次，得到：

所以答案为 $1$。

对于第二组数据，无论如何操作，都无法使三个齿轮状态完全相同，所以答案为 $-1$。