题目描述

長さ $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$ を足したもので置き換える。

输入格式

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

$N$ $A_1$ $:$ $A_N$

输出格式

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

题目大意

有一个长为 $n$ 的序列 $x$，初始时每一项都是 $0$。
给定一个长为 $n$ 的序列 $a$，请用下面的操作将 $x$ 变成 $a$。

• 选择一个 $i$（$1 \le i < N$），将 $x _ {i + 1}$ 变成 $x _ i + 1$。

若无法变成，输出 $-1$，若可以，输出最少的次数。

$1 \leq n \leq 2 \times 10 ^ 5$，$0 \leq a_i \leq 10^9$，$n$ 和 $a_i$ 均为整数。

4
0
1
1
2

3

3
1
2
1

-1

9
0
1
1
0
1
2
2
1
2

8

提示

制約

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

Sample Explanation 1

次のようにして、$X$ を $A$ と等しくすることができます。 - $i=2$ に対して操作する。$X$ は $(0,0,1,0)$ となる。 - $i=1$ に対して操作する。$X$ は $(0,1,1,0)$ となる。 - $i=3$ に対して操作する。$X$ は $(0,1,1,2)$ となる。