{"raw_statement":[{"iden":"statement","content":"小 L 现在在玩一个低配版本的消消乐，该版本的游戏是一维的，一次也只能消除两个相邻的元素。\n\n现在，他有一个长度为 $n$ 且仅由小写字母构成的字符串。我们称一个字符串是可消除的，当且仅当可以对这个字符串进行若干次操作，使之成为一个空字符串。\n\n其中每次操作可以从字符串中删除两个相邻的相同字符，操作后剩余字符串会拼接在一起。\n\n小 L 想知道，这个字符串的所有非空连续子串中，有多少个是可消除的。"},{"iden":"input","content":"输入的第一行包含一个正整数 $n$，表示字符串的长度。\n\n输入的第二行包含一个长度为 $n$ 且仅由小写字母构成的的字符串，表示题目中询问的字符串。"},{"iden":"output","content":"输出一行包含一个整数，表示题目询问的答案。"},{"iden":"note","content":"**【样例 1 解释】**\n\n一共有 $5$ 个可消除的连续子串，分别是 `cc`、`acca`、`cc`、`bccb`、`accabccb`。\n\n**【样例 2】**\n\n见选手目录下的 `game/game2.in` 与 `game/game2.ans`。\n\n**【样例 3】**\n\n见选手目录下的 `game/game3.in` 与 `game/game3.ans`。\n\n**【样例 4】**\n\n见选手目录下的 `game/game4.in` 与 `game/game4.ans`。\n\n**【数据范围】**\n\n对于所有测试数据有：$1 \\le n \\le 2 \\times 10^6$，且询问的字符串仅由小写字母构成。\n\n| 测试点 | $n\\leq$ | 特殊性质 |\n| :----------: | :----------: | :----------: |\n| $1\\sim 5$ | $10$ | 无 |\n| $6\\sim 7$ | $800$ | 无 |\n| $8\\sim 10$ | $8000$ | 无 |\n| $11\\sim 12$ | $2\\times 10^5$ | A |\n| $13\\sim 14$ | $2\\times 10^5$ | B |\n| $15\\sim 17$ | $2\\times 10^5$ | 无 |\n| $18\\sim 20$ | $2\\times 10^6$ | 无 |\n\n特殊性质 A：字符串中的每个字符独立等概率地从字符集中选择。\n\n特殊性质 B：字符串仅由 `a` 和 `b` 构成。"}],"translated_statement":null,"sample_group":[["8\naccabccb\n","5"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}