JOI 君は,長年にわたる家庭菜園の経験を生かして,自宅の庭で新たにジョイ草という植物を育てている.庭には東西方向に並んだ$N$ 個のプランターがあり,西側から順に1 から$N$ までの番号がついている.ジョイ草は全部で$N$ 株あり,それぞれのプランターに1 株ずつ植えてある.
春になって様子を見に行ったJOI 君は,ジョイ草が予想に反して色とりどりの葉を付けていることに気がついた.さらに,ジョイ草が思ったほど生育していないことに気がついた.JOI 君はこれらのことを不思議に思い,本で調べたところ,次のことがわかった:
そこで,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 を出力せよ.
5 RRGYY
2
この入力例では,例えば次のようにすると,葉の色が同じジョイ草が隣り合わないようにすることができる.
このようにすると,ジョイ草の並びはRYRGY のようになる.1 回以下の操作で葉の色が同じジョイ草が隣り合わないようにすることはできないので,2 を出力する.
6 RRRRRG
-1
この入力例では,どのように操作をしても,葉の色が同じジョイ草が隣り合わないようにすることはできない.
20 YYGYYYGGGGRGYYGRGRYG
8
情報オリンピック日本委員会作 『第18 回日本情報オリンピック(JOI 2018/2019) 本選』