题目内容

开馆前，值班员要按晨检清单整理一排连续的阅览席。清单要求：同一种占用状态必须连成一整块，整排至多出现一段空席与一段有人席（允许整排同为一种状态）。台账里空席记为字符 '0'，有人席记为字符 '1'；每次调度只能改动一个座位的状态（请人入座或请人离席），并把该次改动计为 1 次操作。

现给出长度为 $m$ 的台账串 $t$。一次操作可将某一位置上的 '0' 改成 '1'，或将 '1' 改成 '0'。目标形态等价于：存在分界 $p$（$0 \le p \le m$），使得前 $p$ 个座位同色、后 $m-p$ 个座位同为另一种颜色（两种颜色可以相同，即整排同色）。其代价为需要改动的座位个数。请计算把 $t$ 变成合法形态所需的最少操作次数，也就是

其中 $f_{01}(p)$ 表示把前 $p$ 个座位全部改为 '0'、后 $m-p$ 个全部改为 '1' 的改动次数，$f_{10}(p)$ 则对调两种字符。

座位个数 $m$ 满足 $1 \le m \le 200000$。

输入描述

第一行读入一个整数 $m$（$1 \le m \le 200000$），表示阅览席个数。

第二行读入一个长度为 $m$ 的字符串 $t$，仅由字符 '0' 和 '1' 组成，表示当前台账。

输出描述

写出一个非负整数，表示最少操作次数。

样例1

输入

1
1

输出

0

说明

• $m=`1`$，台账为 "1"。
• 仅有一个有人席，已经满足「至多一段 '0' 与至多一段 '1'」。
• 无需调度，答案为 0。

样例2

输入

5
11011

输出

1

说明

• $m=`5`$，台账为 "11011"。
• 取 $p = `5`$ 的 $f_{10}(p)$：整排改为 '1'，只需把第 3 个座位从 '0' 改成 '1'，得到 "11111"，代价为 1。
• 其他分界例如 $p = `2`$ 的 $f_{10}(p)$（前缀 '1'、后缀 '0'）代价为 2，不更优。
• 最少次数为 1。

样例3

输入

7
1001001

输出

2

说明

• $m=`7`$，台账为 "1001001"。
• 取 $p = `1`$ 的 $f_{10}(p)$：前 1 位保持 '1'，后 6 位改为 '0'，得到 "1000000"，需改动第 4、第 7 位，代价为 2。
• 取 $p = `6`$ 的 $f_{01}(p)$：得到 "0000001"，同样代价为 2。
• 整排改为同一字符至少要改 3 次，因此最少次数为 2。