题目描述

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

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

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

输入格式

• 第一行：单个整数 $n$。
• 第二行：$n$ 个字符表示 $b_1b_2\dots b_n$，保证只出现 0 与 1。

输出格式

• 单个整数表示答案

4
1101

1

样例解释 1

改0为1

5
11000

1

样例解释 2

该第二个1为0

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 20$；
• 对于 $60\%$ 的数据，$1\leq n\leq 2000$；
• 对于 $100\%$ 的数据，$1\leq n\leq 500,000$