String

Osnovne informacije

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

Pošlji rešitev



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

We are given a string S of length 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 so that it will not contain the substring "010"?

Input

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

Input limits

  • 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