← 返回题目列表

Codeforces · 924/C

C. 河滨古玩

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

Arkady 决定连续 n 天观察一条河流。每天河流的水位等于某个实际值。

阿尔卡迪每天都会去河边,在水位高度处的河道一侧做一个标记,但如果它与之前做的标记重合,则不会创建新的标记。水并不能洗掉痕迹。 Arkady 每天记下严格高于水位的标记数,在第 i 天该值等于 mi。

定义di为第i天严格低于水位的标记数。你要找出所有日子中 di 的最小可能总和。第一天之前频道上没有任何标记。

输入

第一行包含一个正整数 n (1 ≤ n ≤ 105) — 天数。

第二行包含 n 个空格分隔的整数 m1, m2, ..., mn (0 ≤ mi < i) - 每天严格高于水面的标记数。

输出

输出一个整数——所有日子中严格低于水位的标记数的最小可能总和。

示例

输入 #1

6
0 1 0 3 0 2

输出 #1

6

输入 #2

5
0 1 2 1 2

输出 #2

1

输入 #3

5
0 1 1 2 2

输出 #3

0

注意

在第一个示例中,下图显示了最佳情况。

请注意,在第 3 天,应创建一个新标记,因为如果不创建新标记,则第 4 天不可能有 3 个标记在水面之上。水下标记的总数为 0 + 0 + 2 + 0 + 3 + 1 = 6。

在第二个示例中,下图显示了最佳情况。