分数: 300 点
问题陈述
有 N 多米诺骨牌在数轴上排成一排。的 i第一张多米诺骨牌正站在坐标处 i 并具有高度 A_i.
当 i- 第一个多米诺骨牌向右倒下,所有多米诺骨牌都在坐标之间的范围内 i 和 i+A_i-1,包含在内,落在右侧。
当第一张多米诺骨牌向右倒下时,总共会倒下多少张多米诺骨牌?
约束
- 1\leq N \leq 5\times 10^5
- 1\leq A_i \leq N
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \ldots A_N
输出
输出当第一张多米诺骨牌向右倒下时倒下的多米诺骨牌数量。
示例输入 1
4 3 1 4 1
示例输出 1
4
当第一张多米诺骨牌向右倒下时,第二张和第三张多米诺骨牌也会向右倒下。当第三张多米诺骨牌向右倒下时,第四张多米诺骨牌也倒下。
示例输入 2
9 1 4 1 4 2 1 3 5 6
示例输出 2
1
当第一张多米诺骨牌向右倒下时,不会有其他多米诺骨牌倒下。
示例输入 3
10 5 4 3 2 1 1 2 3 4 5
示例输出 3
5