题目描述

一卷受损档案由字符 A、B、C 组成。档案中的字符可能因墨迹扩散而连续重复。

对档案的一个非空连续片段 $s_l s_{l+1}\ldots s_r$，如果它同时满足以下条件，就称它为一个完整回环：

1. 片段中至少存在一对相邻且不同的字符；
2. 片段的第一个字符与最后一个字符相同，即 $s_l=s_r$；
3. 从左向右阅读片段时，每当相邻字符不同时，它们只能按以下三种方向之一变化：
   • A 变为 B；
   • B 变为 C；
   • C 变为 A。

相邻且相同的字符不受第 $3$ 条限制。片段的两个端点均包含在片段内；只检查完全位于片段内的相邻位置。特别地，全部字符都相同的片段不满足第 $1$ 条。

请统计档案中完整回环的数量。端点 $(l,r)$ 不同的片段分别计数，即使它们的内容相同。

输入格式

从文件 cycletext.in 中读取数据。

第一行输入一个整数 $n$，表示档案长度。

第二行输入一个长度为 $n$ 的字符串 $s$，保证其中每个字符均为 A、B 或 C。

输出格式

输出到文件 cycletext.out 中。

输出一个整数，表示完整回环的数量。

答案不取模，并保证可以用 $64$ 位有符号整数表示。实现时需要使用 $64$ 位整数保存答案和乘积。

样例输入 #1

11
AABCCAAACCB

样例输出 #1

6

样例输入 #2

6
ABCABC

样例输出 #2

3

样例输入 #3

5
AAAAA

样例输出 #3

0

样例解释

样例 #1：

前八个字符中的不同字符依次按照 A、B、C、A 的方向变化。选择开头两个 A 中的任意一个作为左端点，再选择第 $6$ 至第 $8$ 位三个 A 中的任意一个作为右端点，都能得到完整回环，共有 $2\times 3=6$ 个。

第 $8$ 位之后第一次发生的不同字符变化是 A 变为 C，不符合规定，因此不会产生跨过该处的完整回环。

样例 #2：

三个完整回环分别为区间 $[1,4]$、$[2,5]$ 和 $[3,6]$。

样例 #3：

任意片段都没有相邻且不同的字符，所以答案为 $0$。

数据规模与约定

对于所有数据，$1\le n\le 2\times 10^5$。

记

$$B(s)=1+\left|\{i\mid 1\le i<n,\ s_i\ne s_{i+1}\}\right|.$$

本题采用子任务捆绑计分。只有通过某个子任务内的所有测试点，才能获得该子任务的分数。各子任务独立计分。

子任务	分值	额外约束
1	20	$n\le 200$
2	30	$B(s)\le 2000$
3	50	无额外约束

• 输入为单组数据。
• 输出是唯一的，采用标准评测；忽略 token 之间的空白后，输出必须恰好包含一个与标准答案相等的十进制整数。

下发文件

包含本题额外3组大数据的输入与输出文件。

下载三组测试数据，非真实测试数据