D - -1+2-1 Editorial /

Time Limit: 2 sec / Memory Limit: 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_0A_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