/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 700 点
問題文
長さ N の数列 X があり、最初はすべての要素が 0 です。X の i 項目を X_i で表すことにします。
長さ N の数列 A が与えられます。A の i 項目は A_i です。 以下の操作を繰り返すことで X を A と等しくすることができるかどうか判定し、できるなら最小の操作回数を求めてください。
- 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
出力
操作を繰り返すことで X を A と等しくすることができるなら最小の操作回数を、できないなら -1 を出力せよ。
入力例 1
4 0 1 1 2
出力例 1
3
次のようにして、X を A と等しくすることができます。
- 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