At Huahua University, students need to attend classes in $n$ classrooms in a specific order. The $i$-th classroom has an attribute $s_i \in \{0, 1\}$. If $s_i = 1$, it means the classroom has a coffee machine; if $s_i = 0$, it means the classroom does not have a coffee machine.

You are a student at Huahua University. In a classroom with a coffee machine, you can drink a cup of coffee to stay awake. Specifically, after leaving a classroom with a coffee machine, you can carry up to two cups of coffee (one in each hand) to the next classroom, so that even if that classroom does not have a coffee machine, you can stay awake by drinking the coffee you brought with you.

Now you want to know the maximum number of classrooms in which you can drink coffee.

Input

The first line of the input contains an integer $n$.

The next line contains a string $s$ of length $n$, consisting only of the characters 0 and 1, where the $i$-th character $s_i$ describes whether the $i$-th classroom has a coffee machine.

Output

Output a single integer representing the answer.

Examples

Input 1

6
010100

Output 1

5

Input 2

10
0000000110

Output 2

3

Input 3

See the provided files.

Subtasks

For $100\%$ of the data, $1 \le n \le 10^5$.