D - バランス食生活 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

高橋君は健康のために、毎日の食事で野菜と果物をバランスよく摂ることを心がけています。N 日間の食事記録をまとめたところ、長さ N の文字列 S が得られました。S の i 文字目は i 日目の食事内容を表し、次のいずれかです。

  • V : 野菜のみを摂った
  • F : 果物のみを摂った
  • B : 野菜と果物の両方を摂った
  • N : どちらも摂らなかった

i 日目の 野菜スコア v_i と 果物スコア f_i を、食事内容に応じて次のように定めます。

文字 野菜スコア v_i 果物スコア f_i
V 1 0
F 0 1
B 1 1
N 0 0

1 \leq l \leq r \leq N を満たす整数の組 (l, r) に対して、l 日目から r 日目までの区間における野菜スコアの合計 \displaystyle\sum_{i=l}^{r} v_i と果物スコアの合計 \displaystyle\sum_{i=l}^{r} f_i が等しいとき、その区間を バランス期間 と呼びます。両方の合計がともに 0 である場合もバランス期間に含まれます。

バランス期間となる組 (l, r) の個数を求めてください。

制約

  • 1 \leq N \leq 10^6
  • S は長さ N の文字列であり、各文字は V, F, B, N のいずれかである

入力

N
S
  • 1 行目には、日数を表す整数 N が与えられる。
  • 2 行目には、食事記録を表す長さ N の文字列 S が与えられる。

出力

バランス期間の個数を 1 行に出力せよ。

入力例 1

5
VFBNN

出力例 1

10

入力例 2

4
BNNF

出力例 2

6

入力例 3

12
VFBNVFBNVFBN

出力例 3

48

入力例 4

32
VVFFBBNNVVFFBBNNVVFFBBNNVVFFBBNN

出力例 4

244

入力例 5

1
N

出力例 5

1

Score : 400 pts

Problem Statement

Takahashi is trying to eat vegetables and fruits in a balanced way every day for his health. After summarizing his meal records over N days, he obtained a string S of length N. The i-th character of S represents the meal content on day i, and is one of the following:

  • V : Ate only vegetables
  • F : Ate only fruits
  • B : Ate both vegetables and fruits
  • N : Ate neither

The vegetable score v_i and fruit score f_i for day i are defined according to the meal content as follows:

Character Vegetable score v_i Fruit score f_i
V 1 0
F 0 1
B 1 1
N 0 0

For a pair of integers (l, r) satisfying 1 \leq l \leq r \leq N, if the total vegetable score \displaystyle\sum_{i=l}^{r} v_i and the total fruit score \displaystyle\sum_{i=l}^{r} f_i over the interval from day l to day r are equal, then that interval is called a balanced period. This includes the case where both totals are 0.

Find the number of pairs (l, r) that form a balanced period.

Constraints

  • 1 \leq N \leq 10^6
  • S is a string of length N, and each character is one of V, F, B, N

Input

N
S
  • The first line contains an integer N representing the number of days.
  • The second line contains a string S of length N representing the meal records.

Output

Print the number of balanced periods on one line.

Sample Input 1

5
VFBNN

Sample Output 1

10

Sample Input 2

4
BNNF

Sample Output 2

6

Sample Input 3

12
VFBNVFBNVFBN

Sample Output 3

48

Sample Input 4

32
VVFFBBNNVVFFBBNNVVFFBBNNVVFFBBNN

Sample Output 4

244

Sample Input 5

1
N

Sample Output 5

1