Problem Description

JOI-kun has been growing plants in his home garden for many years. He has recently started growing a new plant called Joy Grass in his yard. There are $ N $ planters arranged in a row from west to east, numbered from $ 1 $ to $ N $ in order from the west. There are $ N $ Joy Grass plants, one in each planter.

When JOI-kun checked on the plants in the spring, he noticed that the Joy Grass had grown leaves in various colors, contrary to his expectations. Moreover, he noticed that the plants were not growing as well as he had hoped. Feeling puzzled, JOI-kun researched in a book and found out the following:

• There are three types of Joy Grass, each growing leaves in red, green, or yellow.
• Placing Joy Grass with the same leaf color close to each other inhibits their growth.

Therefore, JOI-kun decided to rearrange the Joy Grass plants so that no two adjacent plants have the same leaf color. He can only swap two adjacent plants at a time. That is, in one operation, JOI-kun can choose any planter $ i $ ($1 \leq i \leq N - 1$) and swap the Joy Grass in planter $ i $ with the one in planter $ i + 1 $. JOI-kun wants to achieve this with the minimum number of operations.

Given the number of Joy Grass plants and the color of the leaves of each plant, write a program to find the minimum number of operations needed to rearrange the plants so that no two adjacent plants have the same leaf color.

Input Format

The input is given from the standard input in the following format:

$ N $ $ S $

$ S $ is a string of length $ N $, where the $ i $-th character ($1 \leq i \leq N$) is R if the leaf color of the Joy Grass in planter $ i $ is red, G if it is green, and Y if it is yellow.

Output Format

Output the minimum number of operations needed to the standard output. If it is impossible to rearrange the plants so that no two adjacent plants have the same leaf color, output $ -1 $ instead.

Sample Input and Output

Sample Input #1

5
RRGYY

Sample Output #1

2

Sample Input #2

6
RRRRRG

Sample Output #2

-1

Sample Input #3

20
YYGYYYGGGGRGYYGRGRYG

Sample Output #3

8

Notes/Hints

Constraints

• $1 \leq N \leq 400$.
• $ S $ is a string of length $ N $.
• Each character in $ S $ is either R, G, or Y.

Subtasks

1. ($ 5 $ points) $N \leq 15$.
2. ($ 55 $ points) $N \leq 60$.
3. ($ 15 $ points) Each character in $ S $ is either R or G.
4. ($ 25 $ points) No additional constraints.

Sample Explanation 1

In this input example, for instance, the following operations can achieve the goal:
- First, swap the Joy Grass in planter $ 3 $ with the one in planter $ 4 $.
- Then, swap the Joy Grass in planter $ 2 $ with the one in planter $ 3 $.
This results in the arrangement RYRGY. It is impossible to achieve the goal with one or fewer operations, so output $ 2 $.

Sample Explanation 2

In this input example, it is impossible to rearrange the plants so that no two adjacent plants have the same leaf color, regardless of the operations performed.

见题面 Input 部分

见题面 Output 部分