← 返回题目列表

AtCoder · agc024_c

C. 序列变得容易

中文机器翻译题面 查看原题

分数: 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