小田的01变换

change.in change.out

题目描述

小田有一个长度为 $n$ 的字符串 $S$，只包含 $0$ 和 $1$ 两种字符。

小田每次可以选择两个索引 $i$ 和 $j$ ($i<j$ 并且在字符串下标范围内)，并满足以下条件之一：

1. 如果区间 [i, j] 中 $1$ 的数量大于 $0$ 的数量，可以把此区间的所有数字都变成 $1$ 。
2. 如果区间 [i, j] 中 $0$ 的数量大于 $1$ 的数量，可以把此区间的所有数字都变成 $0$ 。
3. 如果数量相等，则无法发生变换。

现在小田想知道把整个字符串变成 全 $0$ 或者 全 $1$ 的最少操作次数，如果无解则输出 $-1$ 。

输入描述

输入包含两行。

第一行一个正整数 $n$，表示字符串长度。

第二行输入一个长度为 $n$ 的字符串 $S$，保证输入只包含 $0$、$1$。

输出描述

输出包含一行一个整数，表示最少操作次数，无解则输出 $-1$ 。

输入输出样例

输入 #1

3
011

输出 #1

1

输入 #2

4
1100

输出 #2

2

说明/提示

【样例 1 解释】

第一次：$i=0,j=2$，因为 $1$ 更多，所以全变成 $1$。

【样例 2 解释】

第一次：$i=0,j=2$，字符串变为 $1110$。

第二次：$i=0,j=3$，字符串变为 $1111$。

【数据范围】

对于所有测试数据，有：$1 \le n \le 2 \times 10^{5}$ 。