时间限制：1.0s 内存限制：512.0MB

题目描述

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

输入格式

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

输出格式

一行，一个整数，表示答案。

样例

输入样例1

7
aaaaabb

输出样例1

9

输入样例2

9
babacabab

输出样例2

2

数据范围

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