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。
在第二个示例中,下图显示了最佳情况。