Cowntact Tracing 2

Interview

Time limit2sMemory limit1024 MB

Summary

Find the fewest starting infected cows that, spreading to adjacent cows each night, produce the given infected bitstring.

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

Problem

Farmer John has $N$ cows in a line ( $1 \leq N \leq 3\cdot 10^5$ ). Unfortunately, a sickness is spreading through the herd.

Initially, some cows are infected. Every night, each infected cow spreads the sickness to the cows on its left and right (if they exist). Once a cow is infected, it stays infected.

After some number of nights, Farmer John realizes the problem has gotten out of control, so he tests his cows to see which ones have the sickness. Find the minimum number of cows that could have been infected at the start.

Input

The first line contains $N$ , the number of cows.

The next line contains a bitstring of length $N$ consisting only of 1 and 0. A 1 means the cow is infected after some number of nights, and a 0 means it is not.

Output

Output a single integer: the minimum number of cows that could have been infected at the start.

Examples2

Example 1
Input
```
5
11111
```
Expected output
```
1
```
Example 2
Input
```
6
011101
```
Expected output
```
4
```