题目描述

有一个编号从 $1$ 到 $2^N$ 的 $2^N$ 名参赛者参加的大会。

大会按如下方式进行：

• 首先，给每位参赛者戴上一顶红色或蓝色的帽子。每位参赛者所戴帽子的颜色由字符串 $S$ 给出。具体来说，$S$ 的第 $i$ 个字符（$1 \leq i \leq 2^N$）为 R 时，参赛者 $i$ 戴红帽，为 B 时戴蓝帽。
• 之后，重复以下操作直到只剩下 $1$ 名参赛者：
  • 当前有 $2k$ 名参赛者时，将他们分成 $k$ 组，每组 $2$ 人。分组方式可以自由选择。每组进行比赛，编号较小的参赛者必定获胜，编号较大的淘汰。

你认为，红帽参赛者之间的比赛是“无聊的”比赛。你的目标是，在整个比赛过程中，通过合理分组，使得不会出现任何一场无聊的比赛。

能否实现这个目标取决于字符串 $S$。因此，在比赛开始前，你可以对 $S$ 进行如下操作任意多次（可以为 $0$ 次）：

• 选择 $S$ 中相邻的两个字符，交换它们。

请判断，经过若干次操作后，是否可以实现目标。如果可以，请输出所需的最小操作次数。

输入格式

输入通过标准输入给出，格式如下：

$N$ $S$

输出格式

如果无法实现目标，输出 $-1$。如果可以，输出所需的最小操作次数。

样例 1

输入

2
RRBB

输出

1

样例 2

输入

1
RR

输出

-1

样例 3

输入

4
RBBRRBRBBRBBBRBR

输出

0

样例 4

输入

5
RBRRBRRRBRRRRRRRRRBBBBBBBBBBBBBB

输出

11

说明/提示

限制

• $1 \leq N \leq 18$
• $S$ 是由 R 和 B 组成的长度为 $2^N$ 的字符串。
• 所有输入均为整数。

样例解释 1

如果不进行任何操作，无法实现目标。交换 $S$ 的第 $2$ 个和第 $3$ 个字符，使 $S =$RBRB，则可以实现目标。具体过程如下：

• 参赛者 $1,2,3,4$ 分别戴上红、蓝、红、蓝帽子。
• 将 $4$ 名参赛者分为两组 $(1,4),(2,3)$，此时不会出现无聊的比赛。比赛后，参赛者 $1,2$ 晋级。
• 将 $2$ 名参赛者分为一组 $(1,2)$，此时不会出现无聊的比赛。比赛后，参赛者 $1$ 晋级。
• 因此，答案为 $1$。

由 ChatGPT 4.1 翻译