分数: 700 点
问题陈述
有一个序列 X 长度 N,其中每个元素最初都是 0。让 X_i 表示 i- 第一个元素 X.
给你一个序列 A 长度 N。的 i- 第一个元素 A is 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