/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 600 点
問題文
長さ 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 にすることが可能かどうか判定し，また可能な場合は必要な最小の操作回数を求めてください．
制約
- 3 \leq N \leq 200000
- -100 \leq A_i \leq 100
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられる．
N A_1 A_2 \cdots A_N
出力
A のすべての要素を 0 にすることが不可能なら，-1 と出力せよ．
可能ならば，必要な最小の操作回数を出力せよ．
入力例 1
4 3 0 -1 -2
出力例 1
5
以下のように 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
Score : 600 points
Problem Statement
Given is an integer sequence of length N: A=(A_1,A_2,\cdots,A_N).
You can repeat the operation below any number of times.
- Choose an integer i (1 \leq i \leq N) and add -1, 2, -1 to A_{i-1},A_i,A_{i+1}, respectively. Here, A_0 stands for A_N, and A_{N+1} stands for A_1.
Determine whether it is possible to make every element of A 0. If it is possible, find the minimum number of operations needed.
Constraints
- 3 \leq N \leq 200000
- -100 \leq A_i \leq 100
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \cdots A_N
Output
If it is impossible to make every element of A 0, print -1.
If it is possible to do so, print the minimum number of operations needed.
Sample Input 1
4 3 0 -1 -2
Sample Output 1
5
We can achieve the objective in five operations, as follows.
- Do the operation with i=2. Now we have A=(2,2,-2,-2).
- Do the operation with i=3. Now we have A=(2,1,0,-3).
- Do the operation with i=3. Now we have A=(2,0,2,-4).
- Do the operation with i=4. Now we have A=(1,0,1,-2).
- Do the operation with i=4. Now we have A=(0,0,0,0).
Sample Input 2
3 1 0 -2
Sample Output 2
-1
Sample Input 3
4 1 -1 1 -1
Sample Output 3
-1
Sample Input 4
10 -28 -3 90 -90 77 49 -31 48 -28 -84
Sample Output 4
962