题目描述

给定长度为 $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}$ 的值。

约束条件

• $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