题目描述

有一个长度为 $N$ 的数列 $X$，最开始所有元素均为 $0$。用 $X_i$ 表示 $X$ 的第 $i$ 项。

给定一个长度为 $N$ 的数列 $A$，$A_i$ 表示 $A$ 的第 $i$ 项。请判断是否可以通过以下操作若干次将 $X$ 变为 $A$，如果可以，求最小操作次数。

• 选择一个整数 $i$，满足 $1 \leq i \leq N-1$。将 $X_{i+1}$ 的值替换为 $X_i+1$。

输入格式

输入以如下格式从标准输入读入。

$N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

如果可以通过操作将 $X$ 变为 $A$，输出最小操作次数；否则输出 $-1$。

样例 1

输入

4
0
1
1
2

输出

3

样例 2

输入

3
1
2
1

输出

-1

样例 3

输入

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)$
• 所有输入均为整数。

样例解释 1

可以按如下方式将 $X$ 变为 $A$。

• 对 $i=2$ 进行操作。$X$ 变为 $(0,0,1,0)$。
• 对 $i=1$ 进行操作。$X$ 变为 $(0,1,1,0)$。
• 对 $i=3$ 进行操作。$X$ 变为 $(0,1,1,2)$。

由 ChatGPT 4.1 翻译