410502: GYM104030 C Coffee Cup Combo

Memory Limit:512 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. Coffee Cup Combotime limit per test1 secondmemory limit per test512 megabytesinputstandard inputoutputstandard output

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.

ExamplesInput
10
0100010100
Output
8
Input
10
1100000000
Output
4
Input
1
0
Output
0

加入题单

上一题 下一题 算法标签: