Description

Mr. JOI, an expert in home vegetable gardens, grows a plant called Joy grass in his home garden. In his garden, there are $N$ flowerpots placed from east to west, and the $i$-th one is labeled $i$. Each flowerpot contains one Joy grass plant.

Spring has arrived. Mr. JOI noticed that the Joy grass has grown leaves of various colors as he expected, but he also found that the Joy grass is not growing as fast as he hoped. He looked up information in books and found the following properties of this grass:

• Joy grass has three varieties, which grow red, green, and yellow leaves, respectively.
• If two Joy grass plants of the same color are directly adjacent, their growth speed will slow down.

Therefore, Mr. JOI decided to rearrange the flowerpots so that no two adjacent Joy grass plants have the same color.

The flowerpots are very heavy, so Mr. JOI can only swap two adjacent flowerpots each time. Formally, in one operation, Mr. JOI can choose an $i$ and then swap flowerpots $i$ and $i+1$.

Write a program to compute the minimum number of swaps needed.

Input Format

The first line contains an integer $N$.

The next line contains a string of length $N$, where each character is one of R, G, Y, representing the color of the Joy grass.

Output Format

Output one line containing an integer, the minimum number of operations needed to achieve the goal. If it is impossible, output $-1$.

5
RRGYY

2

6
RRRRRG

-1

20
YYGYYYGGGGRGYYGRGRYG

8

Hint

Sample Explanation

Sample explanation 1:

One valid plan is:

Step 1: Swap the 3rd flowerpot and the 4th flowerpot.

Step 2: Swap the 2nd flowerpot and the 3rd flowerpot.

It can be proven that there is no plan with fewer operations.

Sample explanation 2:

It can be proven that no matter how you move them, the goal cannot be achieved.

Subtasks

Subtask 1 (5 points): $N \le 15$.

Subtask 2 (55 points): $N \le 60$.

Subtask 3 (15 points): The string contains only R, G.

Subtask 4 (25 points): $N \le 400$.

Translated by ChatGPT 5