Description

给定一个 01 序列 $b_1b_2…b_n$，01 的意思就是这个数列里只有 0 与 1。

我们可以修改该序列的任意一个数字，可以将 0 变成 1，也可以将 1 变成 0，注意不能删除或增加数字。

请问，最少需要修改多少数字才能让给定的序列中不含有特定的一个子串 $110$。

Input Format

• 第一行：单个整数 $n$。
• 第二行：$n$ 个字符表示 $b_1b_2…b_n$，保证只出现 0 与 1。
• 对于 $30\%$ 的数据，$1≤n≤20$；
• 对于 $60\%$ 的数据，$1≤n≤2000$；
• 对于 $100\%$ 的数据，$1≤n≤500,000$

Output Format

单个整数表示答案

4
1101

1

5
11000

1

Hint

样例一说明：改0为1 样例二说明：改第二个1为0