AtCoder Grand Contest 024

C - Sequence Growing Easy


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 1024MB

配点 : 700

問題文

長さ N の数列 X があり、最初はすべての要素が 0 です。Xi 項目を X_i で表すことにします。

長さ N の数列 A が与えられます。Ai 項目は A_i です。 以下の操作を繰り返すことで XA と等しくすることができるかどうか判定し、できるなら最小の操作回数を求めてください。

  • 1\leq i\leq N-1 なる整数 i を選ぶ。X_{i+1} の値を X_i の値に 1 を足したもので置き換える。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9(1\leq i\leq N)
  • 入力はすべて整数である

入力

入力は以下の形式で標準入力から与えられる。

N
A_1
:
A_N

出力

操作を繰り返すことで XA と等しくすることができるなら最小の操作回数を、できないなら -1 を出力せよ。


入力例 1

4
0
1
1
2

出力例 1

3

次のようにして、XA と等しくすることができます。

  • i=2 に対して操作する。X(0,0,1,0) となる。
  • i=1 に対して操作する。X(0,1,1,0) となる。
  • i=3 に対して操作する。X(0,1,1,2) となる。

入力例 2

3
1
2
1

出力例 2

-1

入力例 3

9
0
1
1
0
1
2
2
1
2

出力例 3

8

Score : 700 points

Problem Statement

There is a sequence X of length N, where every element is initially 0. Let X_i denote the i-th element of X.

You are given a sequence A of length N. The i-th element of A is A_i. Determine if we can make X equal to A by repeating the operation below. If we can, find the minimum number of operations required.

  • Choose an integer i such that 1\leq i\leq N-1. Replace the value of X_{i+1} with the value of X_i plus 1.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9(1\leq i\leq N)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1
:
A_N

Output

If we can make X equal to A by repeating the operation, print the minimum number of operations required. If we cannot, print -1.


Sample Input 1

4
0
1
1
2

Sample Output 1

3

We can make X equal to A as follows:

  • Choose i=2. X becomes (0,0,1,0).
  • Choose i=1. X becomes (0,1,1,0).
  • Choose i=3. X becomes (0,1,1,2).

Sample Input 2

3
1
2
1

Sample Output 2

-1

Sample Input 3

9
0
1
1
0
1
2
2
1
2

Sample Output 3

8

Submit提出する