← 返回题目列表

AtCoder · abc174_d

D. 祭坛

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

分数: 400 点

问题陈述

祭坛供奉着 N 石头从左到右排列成一排。的颜色 i左起第 3 块石头 (1 \leq i \leq N) 作为一个角色给予你 c_i; R 代表红色和 W 代表白色。

您可以按任意顺序执行任意次数的以下两种操作:

  • 选择两颗棋子(不一定相邻)并交换它们。
  • 选择一颗宝石并更改其颜色(从红色变为白色,反之亦然)。

据算命师说,白石放在红石左边会带来灾难。至少需要多少次操作才能达到没有这样白石的情况?

约束

  • 2 \leq N \leq 200000
  • c_i is R or W.

输入

输入由标准输入按以下格式给出:

N
c_{1}c_{2}...c_{N}

输出

打印一个整数,表示所需的最少操作数。


示例输入 1

4
WWRR

示例输出 1

2

例如,下面的两个操作就可以达到目的。

  • 交换 1-st 和 3- 从左边起第一个石头,导致 RWWR.
  • 更改颜色 4从左边算起第一个石头,结果是 RWWW.

示例输入 2

2
RR

示例输出 2

0

可能存在不需要任何操作的情况。


示例输入 3

8
WRWWRWRR

示例输出 3

3