AT_joi2019ho_c たのしいたのしいたのしい家庭菜園 (Growing Vegetables is Fun 3)

JOI 君凭借多年的家庭园艺经验，在自家院子里新种植了一种名为“ジョイ草”的植物。院子里东西方向依次排列着 $N$ 个花盆，从西侧开始依次编号为 $1$ 到 $N$。共有 $N$ 株ジョイ草，每个花盆里各种植一株。 春天到来时，JOI 君前去查看，发现ジョイ草的叶子出乎意料地呈现出各种颜色。同时，他还注意到ジョイ草的生长并不如预期。JOI 君对此感到疑惑，查阅书籍后得知如下信息： - ジョイ草共有 $3$ 种类型，分别长有红色、绿色和黄色的叶子。 - 如果相同颜色叶子的ジョイ草靠得太近，会抑制它们的生长。 因此，JOI 君决定重新排列ジョイ草，使得相同颜色叶子的ジョイ草不会相邻。此时，JOI 君只能交换相邻的两株ジョイ草。也就是说，每次操作可以任选一个 $i$（$1 \leq i \leq N-1$），将第 $i$ 个花盆和第 $i+1$ 个花盆中的ジョイ草交换。 JOI 君希望用尽可能少的操作次数，使得相同颜色叶子的ジョイ草不再相邻。 给定ジョイ草的数量以及每株ジョイ草叶子的颜色，请编写程序，求出最少需要多少次操作才能实现目标。如果无法实现，请输出 $-1$。

输入从标准输入中给出，格式如下： > $N$ $S$ $S$ 是一个长度为 $N$ 的字符串，第 $i$ 个字符（$1 \leq i \leq N$）表示第 $i$ 个花盆中ジョイ草的叶子颜色，红色为 `R`，绿色为 `G`，黄色为 `Y`。

输出一个整数，表示最少需要的操作次数。如果无法实现目标，则输出 $-1$。

### 限制条件 - $1 \leq N \leq 400$。 - $S$ 是长度为 $N$ 的字符串。 - $S$ 的每个字符都是 `R`、`G` 或 `Y` 之一。 ### 子任务 1. （5 分）$N \leq 15$。 2. （55 分）$N \leq 60$。 3. （15 分）$S$ 的每个字符都是 `R` 或 `G` 之一。 4. （25 分）无额外限制。 # 样例说明 1 在本输入样例中，可以如下操作，使得相同颜色的ジョイ草不再相邻： - 首先，将第 $3$ 个花盆和第 $4$ 个花盆中的ジョイ草交换。 - 然后，将第 $2$ 个花盆和第 $3$ 个花盆中的ジョイ草交换。 这样，ジョイ草的排列变为 `RYRGY`。无法通过 $1$ 次或更少的操作实现目标，因此输出 $2$。 # 样例说明 2 在本输入样例中，无论如何操作，都无法使得相同颜色的ジョイ草不再相邻。 由 ChatGPT 4.1 翻译