#2929. stong9070奇遇记之珠子

stong9070奇遇记之珠子

背景

stong9070者,三国M国之谋士也。旅行间,得五彩石,其色灿烂夺目,见而心动,欲究其故。忽有光起,被吸入密室。遍寻出口,竟无所得。乃于无人之隅,见一桌置珠,旁有图示,需按色排列,乃得出路。无奈,依图重排之。

题目描述

桌子上放着从左到右排列的NN颗珠子。每颗珠子有一种颜色,R代表红色,W代表白色;从左起第ii颗珠子的颜色(1iN1≤i≤N)为cic_i

您可以按任何顺序多次执行以下两种操作:

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

根据规则,当白色珠子出现在红色珠子的左边就不会出现出口(WR),stong9070为了要走出密室,至少需要多少次操作才能达到没有这样一种组合的情况?

输入格式

第一行一个整数NN

第二行只包含NN个W或者R的一行字符串cic_i

输出格式

输出一个整数,表示所需的最小操作次数

样例

4
WWRR
2

样例解释

下面的两个操作将实现目标

  • 交换第1和第3颗珠子,得到RWWR
  • 更改第4颗珠子的颜色,生成RWWW
2
RR
0
8
WRWWRWRR
3

数据范围

  • 2N2000002 \leq N \leq 200000
  • ci[W,R]c_i \in [W,R]