← 返回题目列表

Codeforces · 1238/D

D. AB 弦

中文机器翻译题面 查看原题

如果字符串 $$$t_1t_2 \dots t_k$$$ 是好的,如果该字符串的每个字母属于至少一个长度大于 1 的回文。

回文是向后读与向前读相同的字符串。例如,字符串 A、BAB、ABBA、BAABBBAAB 是回文,但字符串 AB、ABBBAA、BBBA 不是回文。

以下是一些好的字符串示例:

- $$$t$$$ = AABBB (字母 $$$t_1$$$、$$$t_2$$$ 属于回文 $$$t_1 \dots t_2$$$,字母 $$$t_3$$$、$$$t_4$$$、$$$t_5$$$ 属于回文 $$$t_3 \dots t_5$$$);
- $$$t$$$ = ABAA(字母$$$t_1$$$、$$$t_2$$$、$$$t_3$$$属于回文$$$t_1 \dots t_3$$$,字母$$$t_4$$$属于回文$$$t_3 \dots t_4$$$);
- $$$t$$$ = AAAAA(所有字母都属于回文 $$$t_1 \dots t_5$$$);

给定一个长度为 $$$n$$$ 的字符串 $$$s$$$,仅包含字母 A 和 B。

你必须计算字符串$$$s$$$的好子串的数量。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — 字符串 $$$s$$$ 的长度。

第二行包含字符串 $$$s$$$,由字母 A 和 B 组成。

输出

打印一个整数——字符串$$$s$$$的好子串的数量。

示例

输入 #1

5
AABBB

输出 #1

6

输入 #2

3
AAA

输出 #2

3

输入 #3

7
AAABABB

输出 #3

15

注意

在第一个测试用例中,有六个好的子字符串: $$$s_1 \dots s_2$$$、$$$s_1 \dots s_4$$$、$$$s_1 \dots s_5$$$、$$$s_3 \dots s_4$$$、$$$s_3 \dots s_5$$$ 和 $$$s_4 \dots_5$$$。

在第二个测试用例中,有三个好的子字符串:$$$s_1 \dots s_2$$$、$$$s_1 \dots s_3$$$ 和 $$$s_2 \dots s_3$$$。