等价消除

题目描述 小 A 有一个仅包含小写英文字母的字符串 S。 对于一个字符串，如果能通过每次删去其中两个相同字符的方式，将这个字符串变为空串，那么称这个字符串是可以被等价消除的。 小 A 想知道 S 有多少子串是可以被等价消除的。 一个字符串 S~1~ 是 S 的子串，当且仅当删去 S 的某个可以为空的前缀和某个可以为空的后缀之后，可以得到 S~1~。

输入格式 第一行，一个正整数 N，表示字符串的长度。 第二行，一个仅包含小写英文字母的字符串 S。

输入样例 1

7
aaaaabb

输出样例 1

9

输入样例 2

9
babacabab

输出样例 2

2

数据范围 对于 20% 的测试点，保证 S 中仅包含 a 和 b 两种字符。 对于另外 20% 的测试点，保证 1<= |N| <= 2000。 对于所有测试点，保证 1<= |N| <= 2 × 10^5^。