Growing Vegetables is Fun 3

JOI-kun, an expert at home gardening, grows a vegetable called Joy grass in his home garden. In his garden, N flowerpots are lined up in the east-west direction. The flowerpots are numbered 1, ..., N from the west end. There are N Joy grasses, with one planted in each flowerpot.

In the spring, JOI-kun found that, contrary to his expectations, the Joy grasses had produced leaves of various colors. He also learned that the Joy grasses had not grown as much as he expected. He looked through some books and found the following facts.

• There are 3 kinds of Joy grass, producing red, green, or yellow leaves.
• If Joy grasses with the same leaf color are placed close together, their growth is hindered.

So JOI-kun decided to rearrange the flowerpots so that no two Joy grasses with the same leaf color are adjacent. The flowerpots are so heavy that in a single operation JOI-kun can only swap the two Joy grasses in neighboring flowerpots. In other words, what JOI-kun can do in a single operation is choose an arbitrary flowerpot i (1 ≤ i ≤ N − 1) and swap the Joy grasses in flowerpots i and i + 1.

Write a program that, given the number of Joy grasses and their colors, computes the minimum number of operations needed to rearrange the Joy grasses so that no two Joy grasses with the same leaf color are adjacent.

Read the following data from the standard input.

N
S

S is a string of length N. Its i-th (1 ≤ i ≤ N) character is R, G, or Y when the leaf color of the Joy grass in flowerpot i is red, green, or yellow, respectively.

Print a single line containing the minimum number of operations needed to rearrange the Joy grasses so that no two Joy grasses with the same leaf color are adjacent. If such a rearrangement is impossible, print −1 instead.

• 1 ≤ N ≤ 400.
• S is a string of length N.
• Each character of S is R, G, or Y.