正确思路

• 把$s$按相同字符分段，得到段长序列$a_1,a_2,\ldots,a_k$。

• 关键等价：每一轮只在相邻段边界处生效，右侧段首被删$1$个；当中间段清空后，相邻同字符段会合并，后续每轮“只剩下的边界”继续各删$1$。

• 正确的聚合方式是“偶数段前缀余额”：

  • 维护余额$B$表示“到当前为止，仍需被清掉的偶数段总量”（还未被后面的奇数段抵消）。

  • 从左到右处理分段：

    • 若是偶数段（$a_2,a_4,\ldots$），令$B\leftarrow B+a_i$。

题目内容

现在有$n$条$Plog$ 在首页上排成一列，队尾在下侧，队头在上侧。用长度为$n$的 $01$ 串$s=s_1s_2...s_n$表示这条队列，其中:

• 若$s=1$，则第$i$条 $Plog$属于美食;
• 若$s=0$，则第$i$条 $Plog$属于旅行。

一共会进行无限轮互评操作，每一轮:

• 所有$Plog$的拥有者同时向队头(右侧)互评;

• 互评只会影响每条$Plog$右侧的第一个异属性$Plog$，如果右侧没有异属性$Plog$，则不会产生互评操作;

• 每轮所有互评动作并行计算，然后一次性将所有已经有评论的$Plog$移出，形成新队列再进入下一轮;同一条 $Plog$ 在一轮可能收获多条评价。

显然，无限进行下去，终究会出现不再有互评发生的情况。求整个过程中共有多少条$Plog$收获评价。

输入描述

第一行输入一个整数$n(1≤n≤10^5)$，表示$Plog$ 数量。

第二行输入一个长度为$n$且只由字符'$0$'和'$1$'构成的字符串$s$，表示$Plog$ 的属性分布，其中$s_i$为从左向右第$i$条$Plog$的属性。

输出描述

输出一个整数，表示所有互评结束后共有多少条$Plog$收获评价。

样例1

输入

5
11101

输出

2

说明

在这个样例中:第一轮，第三条('$1$')评论第四条('$0$')，第四条('$0$')评论第五条('$1$')，共$2$条$Plog$收获评论；剩余前三条$Plog$拼接为"$111$"，此时剩下的全是美食$Plog$，不再发生互评现象。

样例2

输入

10
1100010101

输出

8

说明

在这个样例中，"$1100010101$"→"$1100$"→"$110$"→"$11$"，共有$8$条$Plog$被评论。