問題文

N 個の草が一列に並んでおり、1 から N までの番号が付けられています。 各草の高さは 1 以上の整数値で表され、それについて次の情報 S_1,S_2,\cdots,S_{N-1} が分かっています。

• S_i = 'A' のとき: 草 i より草 i + 1 の方が真に高い
• S_i = 'B' のとき: 草 i より草 i + 1 の方が真に低い

N 個の草の高さの合計として考えられる最小値を出力してください。

制約

• 1 \leq N \leq 3000
• N は整数
• S は 'A' および 'B' のみからなる N-1 文字の文字列

入力例 1

7
AABBBA

出力例 1

15

草の高さがそれぞれ 1, 2, 4, 3, 2, 1, 2 となっている状態が、草の高さの合計が最小となります。