251.等价消除

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

第一⾏ ，一个正整数 S ，表⽰字符串 S 的长度。 第⼆⾏ ，一个仅包含⼩写英⽂字母的字符串 S。

一⾏ ，一个整数 ，表⽰答案。

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