# String

### Osnovne informacije

Omejitve
• Čas: 1 s
• Spomin: 128 MB
Avtor:
• Vid Kocijan
• UPM 2018

### Pošlji rešitev

Source: (Auto) text C C++ Pascal Java Python 2 Python 3 Perl C# Prolog (SWI) Ruby

Tvoji rezultati.
 Nisi poslal še nobene rešitve.
Več »

We are given a string S$S$ of length n$n$ that consists of zeros and ones. We would like to modify it in such a way that it will not contain the substring "010". (A substring is a subsequence of consecutive characters.) The only allowed operations is the inversion of individual bits (i.e. replacement of a '1' with a '0' or replacement of a '0' with a '1'). What is the minimal number of replacements that are needed to modify string S$S$ so that it will not contain the substring "010"?

## Input

The first line contains integer n$n$, i.e. the length of S$S$. The second line contains the string S$S$ which consists of zeros and ones.

### Input limits

• 1 \leq n \leq 10^5$1 \leq n \leq 10^5$

## Output

Output one number – the minimal number of required operations.

## Example

### Input

7
0101010

### Output

2

### Comment

In the above example we may obtain the string "0001110" by two replacements. It does not contain the substring "010".

Tip: Log in to
• submit and test your solution
• post or read questions and answers about this task