As a joke, cookies in a straight line in front of the parrot. likes cookies, so she wants to get as many of these cookies as possible. However, decided that this was too easy. So, each cookie in the line of cookies was given a value , meaning that if takes the cookie they cannot take any of the next cookies. What is the maximum number of cookies can get?
the parrot decided to placeInput Specification
The first line will contain one integer . The next line will contain space-separated integers .
Output Specification
One line, containing the maximum number of cookies
can get.Subtasks
Subtask 1 [20%]
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