Problem Description

Farmer John has $N$ cows lined up in a row ($1 \leq N \leq 3\cdot 10^5$). Unfortunately, a disease is spreading.

Initially, some cows are infected. Every night, infected cows spread the disease to the cows immediately to their left and right (if those cows exist). Once a cow is infected, she remains infected forever.

After some number of nights, Farmer John realizes the situation is out of control, so he tests the cows to determine which cows are infected. Please find the minimum possible number of cows that could have been infected initially.

Input Format

The first line contains an integer $N$, the number of cows Farmer John has.

The next line contains a bit string of length $N$ consisting of $1$ and $0$. A $1$ indicates an infected cow, and a $0$ indicates a cow that is still uninfected after some number of nights.

Output Format

Output a single integer, the minimum possible number of cows that could have been infected initially.

5
11111

1

6
011101

4

Hint

Sample Explanation 1

Suppose only the middle cow is infected initially. Then the cows will be infected in the following order:

• Night $0$: $00100$ (the third cow is infected at the start)
• Night $1$: $01110$ (the second and fourth cows are now infected)
• Night $2$: $11111$ (the first and fifth cows are now infected)
• Night $3$: $11111$ (all cows are already infected, and no new cows are infected)
• ……

After two or more nights, the cows' state matches the input state. There are also many other initial states and numbers of nights that could lead to the input state, for example:

• Night $0$: $10001$
• Night $1$: $11011$
• Night $2$: $11111$

Or:

• Night $0$: $01001$
• Night $1$: $11111$

Or:

• Night $0$: $01000$
• Night $1$: $11100$
• Night $2$: $11110$
• Night $3$: $11111$

In all of these initial states, at least one cow is infected.

Sample Explanation 2

The only initial state and number of nights that could lead to this final state are: no nights have passed, and the four infected cows in the input were already infected from the very beginning.

Test Point Properties

• Test points $3-7$ satisfy $N \le 1000$.
• Test points $8-12$ have no additional constraints.

Translated by ChatGPT 5