题目描述

这是由1498题提取出来的一个题目

对于一个只有1和0组成的串，我们对其进行有规则的删除操作，直到删空。

删除规则:每次只能删除连续重复出现的1或0 ,（单个出现的1或0也可以看成重复出现的）。 然后把删除操作后剩下的两个串拼起来，继续按删除规则删除。

重复上述步骤直到删空

例如 对于10010010这个串

我们可以这样删除 先删去1~~00~~10010 ，然后串变成了110010

然后我们可以删除11001~~0~~， ，然后串变成了11001

然后我们可以删除11~~00~~1， ，串变成了111

然后我们可以删除~~111~~， ，然后空了

我们进行了4次规则删除操作，才删空。

我们想知道对于一个任意给出的“1” “0”串最少几次规则删除操作才能将其删空。

输入格式

第一行一个整数n表示 “0” “1” 串的长度

第二行一个长度n的 “0” “1” 组成的串 1<=n<=1000000;

输出格式

输出最少的删除操作次数

样例

3 
101

2

7 
11111111

1

提示

QLU _ 高晓飞

原题是https://codeforces.com/contest/1550/problem/B

改编的题目，数据可能出错，欢迎指出