← 返回题目列表

Codeforces · 719/B

B. 阿纳托利和蟑螂

中文机器翻译题面 查看原题

阿纳托利和许多其他学生一样住在大学宿舍里。如您所知,蟑螂也与学生一起生活在那里。蟑螂可能有两种颜色:黑色和红色。阿纳托利的房间里住着n只蟑螂。

阿纳托利刚刚让他所有的蟑螂形成一条线。由于他是一个完美主义者,他希望队列中的蟑螂颜色能够交替变化。他有一罐黑色油漆和一罐红色油漆。在一轮中,他可以交换任意两只蟑螂,也可以选择任意一只蟑螂并改变其颜色。

帮助阿纳托利找出使队伍中蟑螂的颜色交替所需的最少圈数。

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 100 000) — 蟑螂的数量。

第二行包含一个长度为n的字符串,由字符“b”和“r”组成,分别表示黑蟑螂和红蟑螂。

输出

打印一个整数 - Anatoly 必须执行的最小移动次数,才能使该行中的蟑螂的颜色交替。

示例

输入 #1

5
rbbrr

输出 #1

1

输入 #2

5
bbbbb

输出 #2

2

输入 #3

3
rbr

输出 #3

0

注意

在第一个样本中,Anatoly 必须交换第三只和第四只蟑螂。他需要 1 回合才能做到这一点。

在第二个示例中,最佳答案是将第二只和第四只蟑螂涂成红色。这需要2回合。

在第三个示例中,行中蟑螂的颜色已经交替,因此答案为 0。