You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

Csvoner 拿到了 $n$ 个神奇的加速珠，每个加速珠要么是红色的要么是蓝色的。

这些加速珠初始排成了一排，第 $i$ 个加速珠的颜色是 $a_i$（r 表示红色，b 表示蓝色）。

很可惜，初始的排列方式有可能无法达到加速效果。只有当加速珠排列程红蓝相间（相邻两个加速珠颜色不一样）时才会有加速效果。

• 比如 rbrbrb、brbrbrb、rb、r 都有加速效果，
• 但是 bbr、rbbr、rr 这些排列方式都没有加速效果。

现在为了让加速珠有加速效果，你可以挑选前面的一些珠子，将其翻转到末尾。请问你最少选择几个珠子才能达到加速效果（如果怎么也无法达到加速效果，输出 -1）。

什么是翻转操作？

如果把前 $k$ 个珠子翻转到末尾，那么效果如下：

• 原串：$a_{1}a_{2}\dots a_{k-1}a_{k}a_{k+1}\dots a_{n}$
• 翻转后：$a_{k+1}a_{k+2}\dots a_{n}a_{k}a_{k-1}\dots a_{2}a_{1}$

输入格式

第一行一个整数 $n$。

接下来一行一个长度为 $n$ 的字符串 $s$。

输出格式

一行一个整数，表示答案。

4
rbbr

2

4
rbrb

0

5
rbbrb

-1

数据规模与约定

对于 $100\%$ 的数据，$1\le n \le 10^6$，$s$ 中仅包含字符 r 与 b。

• 子任务 1（30 分）：保证 $n=3$。
• 子任务 2（30 分）：保证必然有解。
• 子任务 3（30 分）：没有特殊限制。