Problem Background

JOI 2019 Final T3

Due to the large number of data points, only a portion of the data will be evaluated for this problem.

Problem Description

Home gardening expert Mr. JOI grows a plant called Joy Grass in his home garden. In his garden, there are $N$ pots arranged from east to west, numbered $i$ for the $i$-th pot. Each pot contains a Joy Grass plant.

Spring has arrived, and Mr. JOI notices that the Joy Grass has grown leaves of various colors as he expected, but he also finds that the growth rate is not as fast as he hoped. After consulting books, he discovered the following characteristics of the grass:

• Joy Grass comes in three varieties, each producing red, green, and yellow leaves.
• If two Joy Grass plants of the same color are adjacent, their growth rate slows down.

Therefore, Mr. JOI decides to rearrange the pots so that no two adjacent Joy Grass plants have the same color.

The pots are very heavy, so Mr. JOI can only swap two adjacent pots at a time. Formally, Mr. JOI can choose an $i$ and then swap pots $i$ and $i+1$.

Write a program to calculate the minimum number of swaps required.

Input Format

The first line contains an integer $N$.

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

Output Format

Output a single integer, which is the minimum number of operations required to achieve the goal. If it is not possible to achieve the goal, output $-1$.

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

Explanation for Sample $1$:

One valid solution is:

• First step: Swap the third and fourth pots.
• Second step: Swap the second and third pots.

It can be proven that no solution with fewer swaps exists.

Explanation for Sample $2$:

It can be proven that no matter how the pots are moved, the goal cannot be achieved.

For $5\%$ of the data, $N \le 15$.

For $60\%$ of the data, $N \le 60$.

For an additional $15\%$ of the data, the string contains only R and G.

For $100\%$ of the data, $N \le 400$.

见题面 Input 部分

见题面 Output 部分