Coffee Cup Combo

Interview

Time limit1sMemory limit1024 MB

Summary

Given a binary string marking which lecture halls have coffee machines, find the most lectures Jonna can stay awake in while carrying at most two cups.

Level: Medium5 of 10
Topics: Dynamic programming, Greedy
Solved: No attempts yet

Problem

Jonna is a university student who attends $n$ lectures every day. Most lectures are far too simple for an algorithmic expert such as Jonna, so she can stay awake during a lecture only while drinking coffee. She must drink exactly one cup of coffee during each lecture to stay awake.

Some lecture halls have coffee machines, where she can always get coffee. When Jonna leaves a lecture hall, she can carry at most two coffee cups to the following lectures (one in each hand). She cannot hold more than two coffee cups at any time.

Given which lecture halls have coffee machines, compute the maximum number of lectures during which Jonna can stay awake.

Input

The first line contains the integer $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 character is 1 if the $i$ -th lecture hall has a coffee machine, and 0 otherwise.

Output

Print one integer, the maximum number of lectures during which Jonna can stay awake.

Examples3

Example 1
Input
```
10
0100010100
```
Expected output
```
8
```
Example 2
Input
```
10
1100000000
```
Expected output
```
4
```
Example 3
Input
```
1
0
```
Expected output
```
0
```