肥猪的钢琴床
题号:NC214436
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

肥猪很喜欢睡懒觉,与此同时肥猪十分喜欢买各种各样神奇的床。

今天肥猪买了一张很宽很宽的钢琴床,肥猪就在上面滚来滚去。
这张钢琴床十分的有趣,因为它被分为n个部分,每一个部分是凸起来或者凹下去的,可是肥猪十分不喜欢相邻两个位置高低不同,因为他会滚不过去。
肥猪从小就很喜欢这样的一句谚语:猪往高处走,水往低处流,所以肥猪很喜欢凸起来的部分而不喜欢凹下去的部分。
现在肥猪可以把床中的某一些部分拿走,以让剩余部分所有凸起来的部分都是连起来的,这样肥猪就会很开心,因为他又可以滚来滚去了。
肥猪希望移除的部分最少

我们假设0表示某一个位置是凹下去的,1表示某一个位置是凸起来的。

那么
0
1
00111
01111000
11100
都是肥猪喜欢的钢琴床,因为所有凸起来的部分都是连续的

如果是
101
010011
1111101
就是肥猪不喜欢的钢琴床,因为所有凸起来的部分不是连续的
对于第一张床,肥猪可以把第二个位置拿走,这样床就变成了11。
对于第二张床,肥猪可以把第二个位置拿走,这样床就变成了00011。


输入描述:

读入一共有两行,第一行只有一个正整数数n,表示钢琴床有n个部分。
第二行由一个01串组成
* n<=1000000
* 保证01串的长度为n

输出描述:

输出一个正整数表示肥猪最少要拿走的部分的数量
示例1

输入

复制
10
0001111000

输出

复制
0
示例2

输入

复制
3
101

输出

复制
1
示例3

输入

复制
6
010011

输出

复制
1