题目描述
又一次收集完树枝后,RT做了防火工作,这次RT成功的使用了树枝战胜了人马。经过了长时间的痛苦折磨,RT释怀了并决定去海拉卢达陆上狩猎岩石巨人,用岩石巨人的心岩照亮心形湖来祭奠他还未开始就结束的爱情。
假设心形湖由1n个方格构成,RT在每个方格上放了一个心岩,每个心岩有一个照亮范围x,代表着这块心岩可以照亮它左边x个方格和右边x个方格,但不能照亮心岩所在的方格(假如一个心岩在第5个方格,x=2,那么他只能照亮第3,4和第6,7个方格),现在请你求出心形湖有多少个方格被照亮。
输入
第一行一个正整数n,心形湖格子的个数。( 1 ≤ n ≤ 1e6)第二行n个整数,第i个数表示第i个心岩能照亮的范围。(0≤ ≤ 1e9)
输出
一行,一个整数,表示照亮的格子数
样例输入 Copy
5
0 1 0 0 10
样例输出 Copy
4
提示
样例一说明:前四个方格被最后一个心岩照亮
样例二:
输入:
3
样例二说明:第一个方格和第三个方格被第二个格子的心岩照亮,第四个方格被第五个格子的心岩照亮,一共有三个格子被照亮
样例二:
输入:
5 0 1 0 0 1输出:
3
样例二说明:第一个方格和第三个方格被第二个格子的心岩照亮,第四个方格被第五个格子的心岩照亮,一共有三个格子被照亮