/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 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 番目のドミノを右に倒したときに倒れるドミノの個数を出力せよ。
入力例 1
4 3 1 4 1
出力例 1
4
1 番目のドミノが右に倒れると、2,3 番目のドミノも右に倒れます。3 番目のドミノが右に倒れると、4 番目のドミノも倒れます。
入力例 2
9 1 4 1 4 2 1 3 5 6
出力例 2
1
1 番目のドミノを右に倒しても、他のドミノが倒れることはありません。
入力例 3
10 5 4 3 2 1 1 2 3 4 5
出力例 3
5
Score : 300 points
Problem Statement
There are N dominoes standing in a row on a number line. The i-th domino is standing at coordinate i and has height A_i.
When the i-th domino falls to the right, all dominoes in the range between coordinates i and i+A_i-1, inclusive, fall to the right.
How many dominoes will fall in total when the first domino falls to the right?
Constraints
- 1\leq N \leq 5\times 10^5
- 1\leq A_i \leq N
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
Output the number of dominoes that fall when the first domino falls to the right.
Sample Input 1
4 3 1 4 1
Sample Output 1
4
When the first domino falls to the right, the second and third dominoes also fall to the right. When the third domino falls to the right, the fourth domino also falls.
Sample Input 2
9 1 4 1 4 2 1 3 5 6
Sample Output 2
1
When the first domino falls to the right, no other dominoes will fall.
Sample Input 3
10 5 4 3 2 1 1 2 3 4 5
Sample Output 3
5