题目描述

有 $N$ 个格子排成一行。有些格子可能含有一个“令牌”。你会得到一个只由 0 和 1 组成的字符串 $s$，如果 $s$ 的第 $i$ 个字符为 1，则从左起第 $i$ 个格子里有一个令牌，否则没有。

“すぬけ君”想要尽可能多地进行以下操作：每次选择连续的三个格子，记作从左到右的 $X, Y, Z$。进行操作的条件是 $X$ 和 $Z$ 都有令牌，$Y$ 不能有令牌。然后移除 $X$ 和 $Z$ 的这两个令牌，在 $Y$ 上放一个新令牌。

按照最优策略，すぬけ君最多可以进行多少次这种操作？

输入格式

输入通过标准输入给出，格式如下：

$N\ s$

输出格式

输出操作的最大次数。

输入输出样例 #1

输入 #1

7
1010101

输出 #1

2

输入输出样例 #2

输入 #2

50
10101000010011011110001001111110000101010111100110

输出 #2

10

说明/提示

限制

• $1 \leq N \leq 500,\!000$
• $|s| = N$
• $s$ 的每个字符都是 0 或 1。

样例解释 1

例如，可以按以下方法进行两次操作：

• 首先对最后三个格子操作。字符串变为 1010010。
• 然后对最左边的三个格子操作。字符串变为 0100010。

注意操作的顺序很重要，例如如果先对中间三个格子操作，以后就无法再操作了。