题目描述

给定一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\cdots,A_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$，如果可以，请求出所需的最小操作次数。

输入格式

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

$N$ $A_1$ $A_2$ $\cdots$ $A_N$

输出格式

如果无法将 $A$ 的所有元素都变为 $0$，输出 -1。如果可以，输出所需的最小操作次数。

样例 1

输入

4
3 0 -1 -2

输出

5

样例 2

输入

3
1 0 -2

输出

-1

样例 3

输入

4
1 -1 1 -1

输出

-1

样例 4

输入

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

输出

962

说明/提示

限制条件

• $3 \leq N \leq 200000$
• $-100 \leq A_i \leq 100$
• 输入的所有值均为整数

样例解释 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)$。

由 ChatGPT 4.1 翻译