{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"MD","content":"经过你的帮助,Nanakom和Nanakon和Nanakol和Nanakor成功将他们的糖分成了颗数相等的两份。\n\nNanako对此感到很是惊讶,但此时Nanako还在生闷气,并不想接受他们的糖,所以他想到了一个很毒瘤的问题来难倒Nanakom和Nanakon和Nanakol和Nanakor。\n\nNanako拆开了Nanakom和Nanakon和Nanakol和Nanakor的四袋糖,发现一共有n颗。然后他给每颗糖都打上了标记,每颗糖的标记必定是A和B中的一种。现在,Nanako把这n颗糖排成一排,摆出了一个长度为n的,仅由\u0027A\u0027和\u0027B\u0027组成的字符串。\n\nNanako又作出如下定义:一个字符串被称为好的字符串,当且仅当它的每个字符都属于一个长度大于1的回文串中。众所周知,回文串就是从左往右看和从右往左看完全相同的字符串。比如,\"A\", \"BAB\", \"ABBA\", \"BAABBBAAB\"都是回文串,而\"AB\", \"ABBBAA\", \"BBBA\"都不是回文串。\n\n作为参考,Nanako提供了一些好的字符串的例子。\n\u003cul\u003e\n\u003cli\u003e\"AABBB\"(前两个字符属于长度为2的回文串\"AA\",后三个字符属于长度为3的回文串\"BBB\")\u003c/li\u003e\n\u003cli\u003e\"ABAA\"(前三个字符属于长度为3的回文串\"ABA\",最后一个字符属于长度为2的回文串\"AA\")\u003c/li\u003e\n\u003cli\u003e\"AAAAA\"(所有字符都属于长度为5的回文串\"AAAAA\")\u003c/li\u003e\n\u003c/ul\u003e\n\n现在,Nanako向Nanakom和Nanakon和Nanakol和Nanakor提出了他的问题:由n颗糖的给定排列形成的字符串中,有多少个子串是好的字符串。众所周知,原字符串中任意长度的连续一段都是其子串。\n\n这让Nanakom和Nanakon和Nanakol和Nanakor很是为难。Nanakom和Nanakon和Nanakol和Nanakor都太菜了,他们什么都不会,所以他们希望你可以告诉他们Nanako所要求的好的子串有多少个。\n"}},{"title":"Input","value":{"format":"MD","content":"第一行包含一个整数n(1\u003c\u003dn\u003c\u003d3\u0026times;10\u003csup\u003e5\u003c/sup\u003e),代表糖的数量,即字符串长度。\n\n第二行包含一个长度为n的,仅由\u0027A\u0027和\u0027B\u0027构成的字符串,代表这n颗糖的排列构成的字符串。\n"}},{"title":"Output","value":{"format":"MD","content":"输出一个整数,代表字符串s的好的子串的个数。\n"}},{"title":"Example1","value":{"format":"MD","content":"**Input**\n5\nAABBB\n**Output**\n6\n"}},{"title":"Example2","value":{"format":"MD","content":"**Input**\n3\nAAA\n**Output**\n3\n"}},{"title":"Example3","value":{"format":"MD","content":"**Input**\n7\nAAABABB\n**Output**\n15\n"}},{"title":"Note","value":{"format":"MD","content":"在第一个样例中,有6个好的子串:\n\u003cul\u003e\n\u003cli\u003es\u003csub\u003e1\u003c/sub\u003e...s\u003csub\u003e2\u003c/sub\u003e\u003c/li\u003e\n\u003cli\u003es\u003csub\u003e1\u003c/sub\u003e...s\u003csub\u003e4\u003c/sub\u003e\u003c/li\u003e\n\u003cli\u003es\u003csub\u003e1\u003c/sub\u003e...s\u003csub\u003e5\u003c/sub\u003e\u003c/li\u003e\n\u003cli\u003es\u003csub\u003e3\u003c/sub\u003e...s\u003csub\u003e4\u003c/sub\u003e\u003c/li\u003e\n\u003cli\u003es\u003csub\u003e3\u003c/sub\u003e...s\u003csub\u003e5\u003c/sub\u003e\u003c/li\u003e\n\u003cli\u003es\u003csub\u003e4\u003c/sub\u003e...s\u003csub\u003e5\u003c/sub\u003e\u003c/li\u003e\n\u003c/ul\u003e\n在第二个样例中,有3个好的子串:\n\u003cul\u003e\n\u003cli\u003es\u003csub\u003e1\u003c/sub\u003e...s\u003csub\u003e2\u003c/sub\u003e\u003c/li\u003e\n\u003cli\u003es\u003csub\u003e1\u003c/sub\u003e...s\u003csub\u003e3\u003c/sub\u003e\u003c/li\u003e\n\u003cli\u003es\u003csub\u003e2\u003c/sub\u003e...s\u003csub\u003e3\u003c/sub\u003e\u003c/li\u003e\n\u003c/ul\u003e\n"}}]}