D - ABC|ABC|ABC Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

A, B, C からなる長さ N の文字列 S が与えられます。

S を 2 箇所で区切り、3 つの空でない部分文字列に分割します。形式的には、S の k 文字目を S_k とし、1 \leq i < j < N なる整数の組 (i, j) を選び、S を S_1S_2 \ldots S_i, S_{i + 1}S_{i + 2} \ldots S_j, S_{j + 1}S_{j + 2} \ldots S_N の 3 つの部分文字列に分割します。

3 つの部分文字列それぞれが A, B, C をすべて含むような区切り方の個数を求めてください。

制約

  • 3 \leq N \leq 3 \times 10^5
  • N は整数
  • S は A, B, C からなる長さ N の文字列

入力

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

N
S

出力

答えを出力せよ。


入力例 1

12
AABCCABCCBCA

出力例 1

5

| により文字列を区切る位置を表すことにすると、AABC|CAB|CCBCA, AABC|CABC|CBCA, AABC|CABCC|BCA, AABCC|ABC|CBCA, AABCC|ABCC|BCA の 5 通りの区切り方があります。


入力例 2

3
ABC

出力例 2

0

入力例 3

20
BCACABCACACABCAACBCA

出力例 3

65

Score : 400 points

Problem Statement

You are given a string S of length N consisting of A, B, and C.

We split S at two positions to divide it into three non-empty substrings. Formally, let S_k denote the k-th character of S; we choose a pair of integers (i, j) such that 1 \leq i < j < N, and divide S into three substrings S_1S_2 \ldots S_i, S_{i + 1}S_{i + 2} \ldots S_j, and S_{j + 1}S_{j + 2} \ldots S_N.

Find the number of ways to split S such that each of the three substrings contains all of A, B, and C.

Constraints

  • 3 \leq N \leq 3 \times 10^5
  • N is an integer.
  • S is a string of length N consisting of A, B, and C.

Input

The input is given from Standard Input in the following format:

N
S

Output

Print the answer.


Sample Input 1

12
AABCCABCCBCA

Sample Output 1

5

Using | to denote the positions where the string is split, there are five ways to split it: AABC|CAB|CCBCA, AABC|CABC|CBCA, AABC|CABCC|BCA, AABCC|ABC|CBCA, and AABCC|ABCC|BCA.


Sample Input 2

3
ABC

Sample Output 2

0

Sample Input 3

20
BCACABCACACABCAACBCA

Sample Output 3

65