No.805 UMG

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 252
作問者 : sinsincoscossinsincoscos / テスター : tempura_pptempura_pp
5 ProblemId : 2839 / 出題時の順位表

問題文

長さ$N$の'U','M','G'の3種類の文字のみが現れる文字列$S$があります。先頭から$i$番目の文字を$s_i$とします(1-indexedです)。次の1,2の条件を満たす$(i,j,k)$ の組の数を求めてください。
 1. $1\le i\lt j \lt k\le N$かつ$j-i=k-j$
 2. $s_i=$'U',$s_j=$'M',$s_k=$'G'

注意

Python使いの人はPyPy3で提出することを推奨します。

入力

$N$
$S$

$3\le N \le 5000$
$|S|=N$
$S$は'U','M','G'からなる文字列である。

出力

答えを表す数値を1行に出力してください。最後に改行してください。

サンプル

サンプル1
入力
5
UUMGG
出力
2

 $(1,3,5),(2,3,4)$が条件を満たします。

サンプル2
入力
4
UUUU
出力
0

 そもそも'M'や'G'がありません。

サンプル3
入力
10
UUMMGGGUMG
出力
4

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。