题目描述

sstzer 建造了一排有 $N$ 个村民的交易所（$1 \leq N \leq 3\cdot 10^5$）。

最初，sstzer并没有注意到有一些村民已经被感染为僵尸村民。每到夜晚，僵尸村民会将他左右两边的村民感染为僵尸村民（如果他的旁边有村民的话）。一旦村民被感染，他就会变成僵尸村民。

经过一些晚上，sstzer 意识到情况已经失控，但他还是想知道有最初至少有多少只僵尸村民。

输入格式

从文件 $villager.in$ 中读入数据

第一行为一个整数 $N$，即村民交易所中村民的总数（包括僵尸村民）。

接下来一行，包含长度为 $N$ 的由 $0$ 和 $1$ 组成的位串。其中 $0$ 表示一只村民，$1$ 表示一只僵尸村民。

输出格式

输出数据到文件 $villager.out$

输出一个整数，表示最少有多少只村民可能最初被感染了。

样例

5
11111

1

6
011101

4

提示

样例解释 1

假设只有中间的村民最初被感染。那么，村民们将按以下顺序被感染：

• 第 $0$ 晚：$00100$（第三只村民一开始被感染）
• 第 $1$ 晚：$01110$（第二和第四只村民现在被感染了）
• 第 $2$ 晚：$11111$（第一和第五只村民现在被感染了）
• 第 $3$ 晚：$11111$（所有的村民都已经被感染了，没有新的村民被感染）
• ……

经过两个或更多的晚上，村民们的状态即与输入的状态相符。还有许多其他的初始状态和夜晚数量可能导致了输入的状态，例如：

• 第 $0$ 晚：$10001$
• 第 $1$ 晚：$11011$
• 第 $2$ 晚：$11111$

或者：

• 第 $0$ 晚：$01001$
• 第 $1$ 晚：$11111$

或者：

• 第 $0$ 晚：$01000$
• 第 $1$ 晚：$11100$
• 第 $2$ 晚：$11110$
• 第 $3$ 晚：$11111$

所有这些初始状态中至少有一只僵尸村民。

样例解释 2

唯一可能导致这个最终状态的初始状态和夜晚数是：没有经过任何夜晚，输入中的四只僵尸村民都是从最开始就被感染的。

测试点性质

• 测试点 $3-7$ 满足 $N \le 1000$。
• 测试点 $8-12$ 没有额外限制。