← 返回题目列表

AtCoder · abc435_c

E. 多米诺骨牌

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

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