AT_abc441_e [ABC441E] A > B substring

You are given a string $ S $ of length $ N $ consisting of three kinds of characters: `A`, `B`, and `C`. There are $ \dfrac{N(N+1)}2 $ non-empty contiguous substrings of $ S $ . Find how many of them contain more `A`s than `B`s. Note that two substrings are counted separately if they are taken from different positions in $ S $ , even if they are equal as strings. What is a substring?A **substring** of $ S $ is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of $ S $ . For example, `AB` is a substring of `ABC`, but `AC` is not a substring of `ABC`.

The input is given from Standard Input in the following format: > $ N $ $ S $

Print the number of contiguous substrings of $ S $ that contain more `A`s than `B`s.

### Sample Explanation 1 The following eight substrings satisfy the condition: - `A`: 1st to 1st character of $ S $ - `AC`: 1st to 2nd character of $ S $ - `CA`: 5th to 6th character of $ S $ - `CABCA`: 5th to 9th character of $ S $ - `A`: 6th to 6th character of $ S $ - `ABCA`: 6th to 9th character of $ S $ - `CA`: 8th to 9th character of $ S $ - `A`: 9th to 9th character of $ S $ All other substrings do not satisfy the condition, so print `8`. Note that `A` and `CA` can be taken from multiple positions, but they are counted separately if taken from different positions. ### Sample Explanation 2 There may be no substrings that satisfy the condition. ### Constraints - $ 1\le N\le5\times10 ^ 5 $ - $ S $ is a string of length $ N $ consisting of `A`, `B`, and `C`. - $ N $ is an integer.