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

整圈底色（paint）

题目描述

一圈瓷片共有 $n$ 块，沿顺时针方向编号为 $1,2,\ldots,n$。相邻编号的瓷片互相相邻，此外第 $n$ 块与第 $1$ 块也相邻。每块瓷片最初都没有涂色。

上色时，每次可以选择以下一种操作：

1. 用环形刷给整圈瓷片各涂一层颜色。
2. 选择两块相邻瓷片，用双格印章给这两块瓷片各涂一层颜色。

每次操作都恰好增加一层，已经涂上的颜色不能擦去。两种操作各计作一次，均可使用任意非负整数次。

第 $i$ 块瓷片最终必须恰好有 $a_i$ 层颜色。求达到这些要求所需的最少操作次数；若无法达到，报告无解。

输入格式

第一行包含一个整数 $T$，表示测试用例数量。

对于每组测试用例，第一行包含一个整数 $n$，表示瓷片数量；第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，按顺时针编号顺序给出所需层数。

输出格式

对于每组测试用例，输出一行一个整数。若能达到要求，输出最少操作次数；否则输出 $-1$。

样例

样例输入 #1

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

样例输出 #1

4
3
-1
3

样例输入 #2

1
3
1 1 1

样例输出 #2

1

样例输入 #3

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

样例输出 #3

-1
0

样例解释

第一组样例的第一组测试用例中，在瓷片 $1,3$ 上盖两次双格印章，再在瓷片 $2,3$ 上盖两次，便得到 $2,2,4$，共操作 $4$ 次。

第二组测试用例可以直接用环形刷涂 $3$ 次。第三组测试用例要求另外两块瓷片保持 $0$ 层，任何能给第一块上色的操作都会同时给其他瓷片上色，因此无解。

第四组测试用例可以先用环形刷涂一次，再分别在瓷片 $2,3$ 和 $3,4$ 上盖一次双格印章。

数据范围与约定

对于所有数据，保证 $1\le T\le10$，$3\le n\le2\times10^5$，$0\le a_i\le10^9$。同一个测试点中，所有测试用例的 $n$ 之和不超过 $2\times10^5$。

每个测试点 $5$ 分，分档如下：

特殊性质 A：每组测试用例的 $n$ 都是奇数。

特殊性质 B：每组测试用例的 $n$ 都是偶数。