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 there is a coffee machine in this classroom; if $s_i = 0$, there is no 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 at most 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 are carrying.

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

Input

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

The next line contains a string $s$ of length $n$, consisting only of 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.

Subtasks

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

Examples

Input 1

6
010100

Output 1

5

Input 2

10
0000000110

Output 2

3

Input 3

See the provided files.