最少操作次数
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

Bingbong有一个长度为n的字符串S,仅包含01两种字符。

Bingbong每次可以选择两个索引ij(1\leq i<j\leq n),并满足以下条件之一:

1.如果区间 [i,j] 中 1 的数量大于 0 的数量,可以把此区间的所有数字都变成 1

2.如果区间[i,j] 中 0 的数量大于 1 的数量,可以把此区间的所有数字都变成 0

他想知道把整个串变成全 0 或者全 1 的最少操作次数,如果无解,输出-1

输入描述:

第一行一个整数 n(1\leq n\leq 2\times 10^5) ,表示字符串长度。

第二行一个长度为 n 字符串S,保证输入只含 01

输出描述:

一个整数,表示最少操作次数,无解输出 -1
示例1

输入

复制
2
01

输出

复制
-1
示例2

输入

复制
3
011

输出

复制
1