题目描述

Farmer John 有 $N$ 头奶牛排成一列。不幸的是，有一种疾病正在传播。

最初，有一些奶牛被感染。每到夜晚，被感染的奶牛会将疾病传播给它左右两边的奶牛（如果这些奶牛存在的话）。一旦奶牛被感染，她就会持续处于感染状态。

经过一些晚上，Farmer John 意识到情况已经失控，因此他对奶牛进行了检测以确定哪些奶牛感染了疾病。请找出最少有多少头奶牛最初可能感染了这种疾病。

输入

第一行为一个整数 $N$，即 Farmer John 拥有的奶牛数量。

接下来一行，包含长度为 $N$ 的由1和0组成的位串。

其中1表示一头被感染的奶牛，0 表示一头在经过若干晚之后仍未被感染的奶牛。

输出

输出一个整数，表示最少有多少头奶牛可能最初感染了这种疾病。

5
11111

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

所有这些初始状态中至少有一头奶牛被感染。

6
011101

4

样例解释

唯一可能导致这个最终状态的初始状态和夜晚数是：没有经过任何夜晚，输入中的四头感染的奶牛都是从最开始就感染了这种疾病。

提示

测试点3-7满足$N \leq 1000$

测试点8-12满足$3 \times 10^5$