#113. 2017GCOI六年级第六题 幸存者(2.3)

2017GCOI六年级第六题 幸存者(2.3)

说明

      有 n 个人,现在他们从左往右站成一列。第 i 个人的位置为 i,且第 i 个人手里握着一把长度为 L[i]的大刀。指挥者统一指令, n 个人一齐往左边砍去。对于位置为 i, j 的两个人(i<j),如果满足 i ≥ j - L[j],那么位置为 i的人就会被位置为 j 的人砍死。问:最后有几个人生存下来?

输入格式

第一行输入一个整数 n(1≤n≤1000000),表示有 n 个人。
第二行输入 n 个整数,第 i 个整数是 Li(0≤L[i]≤1000000000), L[i]表示第 i个人的大刀长度

输出格式

输出一个整数,表示最后生存下来的人数

样例

提示


样例三生存下来的是:第3、4、10个。