题目描述

有 $N$ 个单元格排列在一行上。其中一些单元格可能包含代币。给定一个由 0 和 1 组成的字符串 $s$。如果 $s$ 的第 $i$ 个字符是 1，则第 $i$ 个单元格（从左数）包含一个代币。否则，它不包含代币。

Snuke 希望尽可能多次地执行以下操作。在每次操作中，他选择三个连续的单元格。假设这些单元格从左到右分别为 $X, Y, Z$。为了使操作有效，$X$ 和 $Z$ 必须包含代币，并且 $Y$ 不得包含代币。然后，他将移除这两个代币，并将一个新的代币放在 $Y$ 上。

如果他以最优的方式执行操作，他可以执行多少次操作？

约束条件

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

输入

输入以以下格式从标准输入给出：

$N$

$s$

输出

输出答案。

示例输入1

7
1010101

示例输出1

2

例如，他可以按照以下方式执行两次操作：

• 在最后三个单元格上执行操作。现在代币的字符串变为 1010010。
• 在前三个单元格上执行操作。现在代币的字符串变为 0100010。

注意，操作的选择是重要的。例如，如果他首先选择中间的三个单元格，他就无法执行更多的操作。

示例输入2

50
10101000010011011110001001111110000101010111100110

示例输出2

10