当前没有测试数据。

本题暂未上传测试数据，目前仅供阅读与练习。

本站练习请使用标准输入/输出；原卷中的文件名仅作原始资料参考。

题目描述

给定一个长度为 $n$、仅由小写字母构成的字符串。一次操作可以删除两个相邻的相同字符，删除后剩余的两部分字符串会拼接在一起。

当且仅当一个字符串可以通过若干次操作变成空字符串时，称它是可消除的。求给定字符串的所有非空连续子串中，有多少个是可消除的。

输入格式

第一行一个正整数 $n$。第二行一个长度为 $n$、仅由小写字母构成的字符串。

输出格式

输出一个整数，表示可消除的非空连续子串数量。

样例 1

输入

8
accabccb

输出

5

数据范围

$1\le n\le2\times10^6$，字符串仅由小写字母构成。

原卷完整题面

以下保留原卷的图示、完整样例解释、分档约束和特殊性质，便于核对。原卷中引用的外部样例文件未随本次题面上传。

下载原卷题面 PDF