codeforces 892 B题 Wrath

Hands that shed innocent blood!

There are n guilty people in a line, the i-th of them holds a claw with length L_i. The bell rings and every person kills some of people in front of him. All people kill others at the same time. Namely, the i-th person kills the j-th person if and only if j < i and j ≥ i - L_i.

You are given lengths of the claws. You need to find the total number of alive people after the bell rings.

Input

The first line contains one integer n (1 ≤ n ≤ 10⁶) — the number of guilty people.

Second line contains n space-separated integers L₁, L₂, ..., L_n (0 ≤ L_i ≤ 10⁹), where L_i is the length of the i-th person's claw.

Output

Print one integer — the total number of alive people after the bell rings.

Examples

Input

4
0 1 0 10

Output

Input

2
0 0

Output

Input

10
1 1 3 0 0 0 2 1 0 3

Output

Note

In first sample the last person kills everyone in front of him.

题意：有 n 个人每两个人之间有一个单位的距离，每个人都有一把长度为 num[i] 的刀可以杀死左边且在武器攻击范围的人（当（j<i&&i-j<=num[i]）时, 可以杀死 j）

思路：第一阶段：本来想：直接枚举每个人，然后向前标记武器攻击范围内的人死亡，（直接向前遍历 num[i] ）,最后遍历一遍数组统计没有死的人的数量

　　　　　　　　交上去的瞬间感觉不好果不其然 TLE 了，还是 T 在了第 9组样例。

　　第二阶段：然后想应该是向前标记的时候，重复标记次数太多，然后加了一个 kill【】数组 Kill[j] == TRUE 表示判断 j 和 j之前的人全被杀死，不用再向前遍历。

　　　　　　　　很自信地交了上去，然后 TLI 在了第 16 组样例

　　第三阶段：在图上认真画图发现最右边的人一定是存活下来的，从右向左被武器覆盖的人全部会被杀死，所以只需要从右边第二个人向前遍历，判断有没有被

　　　　　　　　武器覆盖就好了，没被武器覆盖就存活，否则就死亡，每次向前遍历时记得维护在 j 人向左的武器长度，即：kill_dis = max(kill_dis-1 , num[j])

// TLE 16

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std ;

#define LL long long  
#define maxn 1100000

LL num[maxn] ; 
bool alive[maxn] ;  
bool kill[maxn] ; 

int main(){
    int n ; 
    while(~scanf("%d" , &n)){
        for(int i=1 ; i<= n ; i++){
            scanf("%lld" , &num[i]) ; 
        }
        
        memset(alive , true , sizeof(alive)) ; 
        memset(kill , false , sizeof(kill)) ; 
        kill[0] = true ; 
        
        LL L ; 
        for(int i=1 ; i<=n ; i++){
            L = num[i] ; // 武器长度 
            for(int j = i-1 ; !kill[j] &&j>0 && i - j <=L ; j-- ){
                if(alive[j]){
                    
                    alive[j] = false ; 
                    
                    if(kill[j-1]){
                        kill[j] = true ; 
                    }
                }
            } 
        }
        
        int sum = 0 ; 
        for(int i=1 ; i<=n ; i++){
            if(alive[i]){
                sum ++ ; 
            }
        }

        printf("%d
" , sum ) ; 
    }
    return 0 ; 
}

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
#define maxn 1100000
#define LL long long
LL num[maxn] ; 
int n ; 

void solve(){
    int result = 1 ; // 最右边的那一个人 
    LL kill_dis = num[n-1] ; //武器向左覆盖的长度 
    
    for(int i= n-2 ; i>=0 ; i--){
        if(!kill_dis){
            result ++ ; 
        }
        kill_dis = max(kill_dis - 1 , num[i]) ; 
    }
    printf("%d
" , result) ; 
}

int main(){
    while(~scanf("%d" , &n)){
        for(int i= 0 ; i<n ; i++){
            scanf("%lld" , &num[i] ) ;          
        }
        
        solve() ; 
    }
    return 0 ; 
}