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

JOI 君は，長年にわたる家庭菜園の経験を生かして，自宅の庭で新たにジョイ草という植物を育てている．庭には東西方向に並んだ$N$ 個のプランターがあり，西側から順に1 から$N$ までの番号がついている．ジョイ草は全部で$N$ 株あり，それぞれのプランターに1 株ずつ植えてある．

春になって様子を見に行ったJOI 君は，ジョイ草が予想に反して色とりどりの葉を付けていることに気がついた．さらに，ジョイ草が思ったほど生育していないことに気がついた．JOI 君はこれらのことを不思議に思い，本で調べたところ，次のことがわかった：

• ジョイ草には3 種類あり，それぞれ赤，緑，黄の葉を付ける．
• 葉の色が同じジョイ草を近くに置くと，その成長が阻害されてしまう．

そこで，JOI 君は，ジョイ草を並び替えて，葉の色が同じジョイ草が隣り合わないようにすることにした．このとき，JOI 君は隣り合う2 つのジョイ草を入れ替えることしかできない．つまり，1 回の操作でJOI 君はプランター$i$ ($1 \leq i \leq N - 1$) を任意に1 つ選び，プランター$i$ のジョイ草とプランター$i + 1$ のジョイ草を入れ替えることができる．JOI 君は，できるだけ少ない回数の操作で，葉の色が同じジョイ草が隣り合わないようにしたい．

ジョイ草の数と，それぞれのジョイ草の葉の色が与えられたとき，葉の色が同じジョイ草が隣り合わないように並び替えるために必要な操作回数の最小値を求めるプログラムを作成せよ．

入力

入力は以下の形式で標準入力から与えられる．

$N$
$S$

$S$ は長さ$N$ の文字列で，その$i$ 文字目($1 \leq i \leq N$) は，プランター$i$ に植えてあるジョイ草の葉の色が赤ならばR，緑ならばG，黄ならばY である．

出力

標準出力に，必要な操作回数の最小値を1 行で出力せよ．ただし，葉の色が同じジョイ草が隣り合わないように並び替えることが不可能ならば，代わりに-1 を出力せよ．

制約

• $ 1 \leq N \leq 400$．
• $S$ は長さ$N$ の文字列である．
• $S$ の各文字はR，G，Y のいずれかである．

入出力例

入力例1

5
RRGYY

出力例1

2

この入力例では，例えば次のようにすると，葉の色が同じジョイ草が隣り合わないようにすることができる．

• まず，プランター3 のジョイ草とプランター4 のジョイ草を入れ替える．
• 次に，プランター2 のジョイ草とプランター3 のジョイ草を入れ替える．

このようにすると，ジョイ草の並びはRYRGY のようになる．1 回以下の操作で葉の色が同じジョイ草が隣り合わないようにすることはできないので，2 を出力する．

入力例2

6
RRRRRG

出力例2

-1

この入力例では，どのように操作をしても，葉の色が同じジョイ草が隣り合わないようにすることはできない．

入力例3

20
YYGYYYGGGGRGYYGRGRYG

出力例3

8

情報オリンピック日本委員会作 『第18 回日本情報オリンピック(JOI 2018/2019) 本選』