892B.md (1238B)
1 Source: https://codeforces.com/problemset/problem/892/B 2 3 B. Wrath 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Hands that shed innocent blood! 22 23 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*. 24 25 You are given lengths of the claws. You need to find the total number of alive people after the bell rings. 26 27 Input 28 29 The first line contains one integer *n* (1 ≤ *n* ≤ 106) — the number of guilty people. 30 31 Second line contains *n* space-separated integers *L*1, *L*2, ..., *L**n* (0 ≤ *L**i* ≤ 109), where *L**i* is the length of the *i*-th person's claw. 32 33 Output 34 35 Print one integer — the total number of alive people after the bell rings. 36 37 Examples 38 39 Input 40 41 ``` 42 4 43 0 1 0 10 44 ``` 45 46 Output 47 48 ``` 49 1 50 ``` 51 52 Input 53 54 ``` 55 2 56 0 0 57 ``` 58 59 Output 60 61 ``` 62 2 63 ``` 64 65 Input 66 67 ``` 68 10 69 1 1 3 0 0 0 2 1 0 3 70 ``` 71 72 Output 73 74 ``` 75 3 76 ``` 77 78 Note 79 80 In first sample the last person kills everyone in front of him.