题目描述

给定一个整数序列 $A = (A_1, A_2,\\cdots,A_N)$，长度为 $N$。

可以任意次数地重复以下操作：

• 选择一个整数 $i$ ($1 \\leq i \\leq N$)，将 $A_{i-1}$、$A_i$、$A_{i+1}$ 分别加上 $\-1, 2, -1$。这里 $A_0$ 表示 $A_N$，$A_{N+1}$ 表示 $A_1$。

确定是否可以使得 $A$ 中的每个元素都为 $0$。如果可以，找到所需的最小操作次数。

约束条件

• $3 \\leq N \\leq 200000$
• $\-100 \\leq A_i \\leq 100$
• 输入中的所有值都是整数。

输入

从标准输入中以以下格式给出输入：

$N$

$A_1 \quad A_2 \quad \\cdots \quad A_N$

输出

如果无法使得 $A$ 中的每个元素都为 $0$，则输出 -1。如果可以，则输出所需的最小操作次数。

示例输入 1

4
3 0 -1 -2

示例输出 1

5

我们可以通过以下五个操作达到目标。

• 当 $i=2$ 时进行操作。现在我们的 $A=(2,2,-2,-2)$。
• 当 $i=3$ 时进行操作。现在我们的 $A=(2,1,0,-3)$。
• 当 $i=3$ 时进行操作。现在我们的 $A=(2,0,2,-4)$。
• 当 $i=4$ 时进行操作。现在我们的 $A=(1,0,1,-2)$。
• 当 $i=4$ 时进行操作。现在我们的 $A=(0,0,0,0)$。

示例输入 2

3
1 0 -2

示例输出 2

-1

示例输入 3

4
1 -1 1 -1

示例输出 3

-1

示例输入 4

10
-28 -3 90 -90 77 49 -31 48 -28 -84

示例输出 4

962