翻牌

题目描述

33DAI 在桌上摆了一排 $n$ 张卡片，每张卡片一面写着 $0$、另一面写着 $1$，初始时都写着 $0$ 或 $1$。 他每次可以选出连续的一段卡片，把它们全部翻面（$0$ 变 $1$，$1$ 变 $0$）。

33DAI 想让所有卡片的数字变得完全相同（全是 $0$ 或者全是 $1$）。 请你求出最少需要翻几次。

输入格式

第一行一个整数 $n$。

第二行一个长度为 $n$ 的字符串，只包含 0 和 1，表示每张卡片朝上的数字。

输出格式

输出一个整数，表示最少翻牌次数。

3
010

1

样例 1 解释

翻转第 $2$ 张卡片，变成 000，所有卡片相同。

4
0101

2

样例 2 解释

可以翻转第 $2$ 张和第 $4$ 张（共两次），也可以翻转第 $1 \sim 3$ 张再翻转第 $2$ 张，最少两次。

数据范围

对于所有测试数据，保证 $1 \le n \le 10^6$。

子任务

本题共 20 个测试点，按测试点计分：

每个测试点单独评分，全部测试点的得分之和即为本题得分。