#A0429. 加速

加速

题目描述

33DAI 拿到了 nn 个神奇的加速珠,每个加速珠要么是红色的要么是蓝色的。

这些加速珠初始排成了一排,第 ii 个加速珠的颜色是 aia_ir 表示红色,b 表示蓝色)。

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

  • 比如 rbrbrbbrbrbrbrbr 都有加速效果,
  • 但是 bbrrbbrrr 这些排列方式都没有加速效果。

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

什么是翻转操作?

如果把前 kk 个珠子翻转到末尾,那么效果如下:

  • 原串:a1a2ak1akak+1ana_{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}$

输入格式

第一行一个整数 nn

接下来一行一个长度为 nn 的字符串 ss

输出格式

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

4
rbbr
2
4
rbrb
0
5
rbbrb
-1

数据规模与约定

对于 100%100\% 的数据,1n1061\le n \le 10^6ss 中仅包含字符 rb

  • 子任务 1(30 分):保证 n=3n=3
  • 子任务 2(30 分):保证必然有解。
  • 子任务 3(30 分):没有特殊限制。