問題文
寿司是将「shihari」上放置「配料」的食物。
苹果先生 N 试图通过堆叠个寿司来制作寿司塔。N 个寿司意味着有N 个饭团 N 个配料,总共有 2N 个部分,但我们想按照某个顺序堆叠这些部分。
个寿司 1 种堆叠方法如下 3 种方式。
- 直接堆叠:按饭团、配料的顺序堆叠。
- 颠倒堆叠:按配料、饭团的顺序堆叠。
- 拆开堆叠:将寿司拆开,分开饭团和配料,分别堆叠。
例如,3 个寿司如果想从下往上依次堆“配料、配料、配料、配料”,可以像下面这样堆。
- 个寿司 1 分段堆叠配料。饭团部分留着稍后堆叠。
- 将寿司原样堆放。
- 将寿司翻面后堆放。
- 堆放事先准备好的米饭。
拆开寿司很麻烦,因此小苹果希望尽量减少拆开的寿司数量。请找出为制作寿司塔而拆开的寿司的最小数量。
入力
输入是按以下格式从标准输入给出的。
N S
- 1 行表示寿司的数量的整数。 N (1 ≦ N ≦ 256) 。
- 2 行表示堆放部件顺序的长度。 2N 的字符串 S 。S 是 N 个
0和 我讨厌 N 个1组成的字符串,S 的 i (1≦i≦2N) 个字符是0当为 时表示从下往上堆放第 i 个米饭,1当为 时表示从下往上堆放第 i 个配料。
出力
为制作目标寿司塔而拆开的寿司的最小数量 1 行输出。在输出末尾插入换行符。
入力例1
3 101100
出力例1
1
就像问题文中的例子一样。下图表示了堆放方式的例子,白色的圆表示寿司饭团,红色的矩形表示鱼料。
入力例2
5 0000111011
出力例2
3