01序列

时间限制:1s

空间限制:64MB

题目描述

有一给定的长度为n, 且只包含 '0' 和 '1' 的字符串s, 令sub为s的一个连续子串,且sub的长度至少为 2, 请问至少要插入多少个 '1' 才能保证 sub中1的数量不小于0的数量

输入格式

第一行一个正整数n

第二行一个长度为n的字符串s

样例输入1

3
000

样例输出1

4

样例1解释

000 -> 0110110就能保证任意一个连续子串(长度不小于2)中1的数量不小于0的数量

样例输入2

3
010

样例输出2

1

样例2解释

010 -> 0110

数据范围

对于50% 的数据, 1 ≤ n ≤ 20

对于100%的数据, 1 ≤ n ≤ 50