如果字符串 $$$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$$$。