给定一个仅由小写字母组成的字符串。一次消除操作可以删除其中两个相邻且相同的字符，再将剩余部分拼接。

统计有多少个非空连续子串可以经过若干次消除后变为空串。不同位置的子串视为不同。

输入格式

第一行一个整数 $n$，表示字符串长度。

第二行给出一个长度为 $n$ 的字符串。

输出格式

输出一个整数，表示满足条件的子串数量。

样例 1

8
accabccb

5

数据范围与原题特殊限制

对于所有测试数据有：$1 \leq n \leq 2 \times 10^6$，且询问的字符串仅由小写字母构成。

特殊性质 A：字符串中的每个字符独立等概率地从字符集中选择。

特殊性质 B：字符串仅由 a 和 b 构成。

来源与数据说明

原题页面。以上题意为重新整理的表述，规则、输入输出和约束与原题一致。本题使用独立生成的训练数据，原题测试点表仅说明原比赛范围与特殊性质，本包评分不复刻官方测试点分布。标准输入输出，不要求文件读写。