AB-string

题意翻译

如果一个字符串的每个字母，属于至少一个（长度大于1）的回文串，则称这个字符串为good。 - AABB：（t1，t2属于回文串t1t2；t3，t4属于回文串t3t4t5） - ABAA：（t1,t2,t3属于回文串t1t2t3；t4属于回文串t3t4） - AABB和ABAA都是good 一个长度为n的字符串s（只由字母A,B组成），问s的子串中有多少个good字符串

题目描述

The string $ t_1t_2 \dots t_k $ is good if each letter of this string belongs to at least one palindrome of length greater than 1. A palindrome is a string that reads the same backward as forward. For example, the strings A, BAB, ABBA, BAABBBAAB are palindromes, but the strings AB, ABBBAA, BBBA are not. Here are some examples of good strings: - $ t $ = AABBB (letters $ t_1 $ , $ t_2 $ belong to palindrome $ t_1 \dots t_2 $ and letters $ t_3 $ , $ t_4 $ , $ t_5 $ belong to palindrome $ t_3 \dots t_5 $ ); - $ t $ = ABAA (letters $ t_1 $ , $ t_2 $ , $ t_3 $ belong to palindrome $ t_1 \dots t_3 $ and letter $ t_4 $ belongs to palindrome $ t_3 \dots t_4 $ ); - $ t $ = AAAAA (all letters belong to palindrome $ t_1 \dots t_5 $ ); You are given a string $ s $ of length $ n $ , consisting of only letters A and B. You have to calculate the number of good substrings of string $ s $ .

输入输出格式

输入格式

The first line contains one integer $ n $ ( $ 1 \le n \le 3 \cdot 10^5 $ ) — the length of the string $ s $ . The second line contains the string $ s $ , consisting of letters A and B.

输出格式

Print one integer — the number of good substrings of string $ s $ .

输入输出样例

输入样例 #1

5
AABBB

输出样例 #1

6

输入样例 #2

3
AAA

输出样例 #2

3

输入样例 #3

7
AAABABB

输出样例 #3

15

说明

In the first test case there are six good substrings: $ s_1 \dots s_2 $ , $ s_1 \dots s_4 $ , $ s_1 \dots s_5 $ , $ s_3 \dots s_4 $ , $ s_3 \dots s_5 $ and $ s_4 \dots s_5 $ . In the second test case there are three good substrings: $ s_1 \dots s_2 $ , $ s_1 \dots s_3 $ and $ s_2 \dots s_3 $ .