AT_abc441_e [ABC441E] A > B substring

`A`, `B`, `C` の $ 3 $ 種類の文字からなる長さ $ N $ の文字列 $ S $ が与えられます。 $ S $ の空でない連続する部分文字列は $ \dfrac{N(N+1)}2 $ 個ありますが、そのうち `A` が `B` よりも多く含まれるものはいくつあるか求めてください。 $ 2 $ つの部分文字列は、 $ S $ から取り出す場所が異なれば文字列として等しくても区別して数えることに注意してください。 部分文字列とは $ S $ の**部分文字列**とは、 $ S $ の先頭から $ 0 $ 文字以上、末尾から $ 0 $ 文字以上削除して得られる文字列のことをいいます。 例えば、`AB` は `ABC` の部分文字列ですが、`AC` は `ABC` の部分文字列ではありません。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ S $

$ S $ の連続する部分文字列のうち `A` が `B` よりも多く含まれるものの個数を出力せよ。

### Sample Explanation 1 以下の $ 8 $ つの部分文字列が条件を満たします。 - `A`： $ S $ の $ 1 $ 文字目から $ 1 $ 文字目 - `AC`： $ S $ の $ 1 $ 文字目から $ 2 $ 文字目 - `CA`： $ S $ の $ 5 $ 文字目から $ 6 $ 文字目 - `CABCA`： $ S $ の $ 5 $ 文字目から $ 9 $ 文字目 - `A`： $ S $ の $ 6 $ 文字目から $ 6 $ 文字目 - `ABCA`： $ S $ の $ 6 $ 文字目から $ 9 $ 文字目 - `CA`： $ S $ の $ 8 $ 文字目から $ 9 $ 文字目 - `A`： $ S $ の $ 9 $ 文字目から $ 9 $ 文字目 これら以外の部分文字列は条件を満たさないため、`8` を出力してください。 `A` や `CA` は複数箇所から取り出すことができますが、取り出す場所が異なれば区別して数えることに注意してください。 ### Sample Explanation 2 条件を満たす部分文字列が存在しないこともあります。 ### Constraints - $ 1\le N\le5\times10 ^ 5 $ - $ S $ は `A`, `B`, `C` からなる長さ $ N $ の文字列 - $ N $ は整数