Problem H
Coffee Cup Combo
Jonna is a university student who attends $n$ lectures every day. Since most lectures are way too simple for an algorithmic expert such as Jonna, she can only stay awake during a lecture if she is drinking coffee. During a single lecture she needs to drink exactly one cup of coffee to stay awake.
Some of the lecture halls have coffee machines, so Jonna can always make sure to get coffee there. Furthermore, when Jonna leaves a lecture hall, she can bring at most two coffee cups with her to the following lectures (one cup in each hand). But note that she cannot bring more than two coffee cups with her at any given time.
Given which of Jonna’s lectures have coffee machines, compute the maximum number of lectures during which Jonna can stay awake.
Input
The first line contains the integers $n$ ($1 \leq n \leq 10^5$), the number of lectures Jonna attends.
The second line contains a string $s$ of length $n$. The $i$’th letter is 1 if there is a coffee machine in the $i$’th lecture hall, and otherwise it is 0.
Output
Print one integer, the maximum number of lectures during which Jonna can stay awake.
| Sample Input 1 | Sample Output 1 |
|---|---|
10 0100010100 |
8 |
| Sample Input 2 | Sample Output 2 |
|---|---|
10 1100000000 |
4 |
| Sample Input 3 | Sample Output 3 |
|---|---|
1 0 |
0 |
