小约翰可汗来到了奇葩小国E，发现这里的国王十分痴迷艺术，喜欢对称的东西。
最近国王在研究字符串。当一个字符串上每个字符都属于某个长度大于 1 的回文子串中时，国王会认为其是漂亮的。
例如 "AAABB"、"ABAA" 是漂亮的，而 "ABB" 不是漂亮的。

现在有一个由 'A'、'B' 两种字符构成的长为 n 的字符串 s 。求有多少 s 的子串是被国王认为是漂亮的。

输入包含两行。
第一行包含两个整数 n(1≤n≤300 000) ，表示字符串 s 长度。
第二行包含一个由 'A'、'B' 两种字符构成的长为 n 的字符串 s 。

输出一个整数，表示答案。

5
AABBB

6

样例2输入
3
AAA

样例2输出
3

样例3输入
7
AAABABB

样例3输出
15

在样例1中，子串 s[1]s[2]、s[1]s[2]s[3]s[4]、s[1]s[2]s[3]s[4]s[5]、s[3]s[4]、s[3]s[4]s[5] 是漂亮的。
在样例2中，子串 s[1]s[2]、s[1]s[2]s[3]、s[2]s[3] 是漂亮的。