← 返回题目列表

Codeforces · 892/B

B. 愤怒

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

流无辜血的双手!

有 n 个有罪的人排成一排,其中第 i 个拿着长度为 Li 的爪子。钟声响起,每个人都杀死了面前的一些人。所有人同时杀害他人。即,当且仅当 j < i 且 j ≥ i - Li 时,第 i 个人杀死第 j 个人。

给定了爪子的长度。你需要找出铃声响起后还活着的总人数。

输入

第一行包含一个整数 n (1 ≤ n ≤ 106) — 有罪人数。

第二行包含 n 个空格分隔的整数 L1, L2, ..., Ln (0 ≤ Li ≤ 109),其中 Li 是第 i 个人的爪子的长度。

输出

打印一个整数——铃声响起后还活着的总人数。

示例

输入 #1

4
0 1 0 10

输出 #1

1

输入 #2

2
0 0

输出 #2

2

输入 #3

10
1 1 3 0 0 0 2 1 0 3

输出 #3

3

注意

在第一个样本中,最后一个人杀死了他面前的所有人。