-1+2-1

时间限制：2s
空间限制：1024MB

题目描述

给定一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\ldots,A_N)$。你可以任意多次执行以下操作：

• 选择一个整数 $i$（$1\le i\le N$），分别给 $A_{i-1},A_i,A_{i+1}$ 加上 $-1,2,-1$。

下标按环形理解，即 $A_0$ 表示 $A_N$，$A_{N+1}$ 表示 $A_1$。请判断能否把 $A$ 的所有元素变为 $0$；若能，求最少操作次数。

输入格式

第一行一个整数 $N$。

第二行 $N$ 个整数 $A_1,A_2,\ldots,A_N$。

输出格式

若无法把所有元素变为 $0$，输出 $-1$；否则输出最少操作次数。

样例输入 1

4
3 0 -1 -2

样例输出 1

5

样例输入 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

数据范围

• $3\le N\le 2\times10^5$；
• $-100\le A_i\le100$。