Parrots and Cookies

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 512M

Author:
Problem type

As a joke, teacycart the parrot decided to place N cookies in a straight line in front of dulldesk the parrot. dulldesk likes cookies, so she wants to get as many of these cookies as possible. However, teacycart decided that this was too easy. So, each cookie in the line of cookies was given a value x (0 \leq x \leq 30), meaning that if dulldesk takes the cookie they cannot take any of the next x cookies. What is the maximum number of cookies dulldesk can get?

Input Specification

The first line will contain one integer N (1 \leq N \leq 10^6). The next line will contain N space-separated integers x_1, x_2, \ldots, x_N (0 \leq x_i \leq 30).

Output Specification

One line, containing the maximum number of cookies dulldesk can get.

Subtasks

Subtask 1 [20%]

N \leq 10^2

x_i \leq 2

Subtask 2 [80%]

No additional constraints.

Sample Input 1

4
0 1 1 2

Sample Output 1

3

Sample Input 2

6
0 1 1 0 2 1

Sample Output 2

4

Comments

There are no comments at the moment.