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$.


-----Input-----

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.


-----Output-----

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


-----Examples-----
Input
5
AABBB

Output
6

Input
3
AAA

Output
3

Input
7
AAABABB

Output
15



-----Note-----

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$.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
s = input()
tab = []
count = 1
for i in range(1, n):
	if s[i] == s[i-1]:
		count += 1
	else:
		if count > 0:
			tab.append(count)
		count = 1
if count > 0:
	tab.append(count)
dis = 0
k = len(tab)
if k == 0 or k == 1:
	dis = 0
else:
	dis += tab[1]
	dis += tab[-2]
	dis -= (k-1)
	for i in range(1, k - 1):
		dis += tab[i-1]
		dis += tab[i+1]
print(n*(n-1)//2 - dis)

from sys import *
from heapq import *
from lib2to3.pgen2.token import MINUS


n = int(input())

S = input()

minus = n
curA = 0
curB = 0
for s in S:
    if s == 'A':
        if curB != 0:
            minus += curB
            curB = 0
            curA = 1
        else:
            curA += 1
    
    else:
        if curA != 0:
            minus += curA
            curA = 0
            curB = 1
        else:
            curB += 1
curA, curB = 0, 0
for i in range(n - 1, -1, -1):
    s = S[i]
    if s == 'A':
        if curB > 1:
            
            minus += curB - 1
            curB = 0
            curA = 1
        elif curB == 1:
            curB = 0
            curA = 1
        else:
            curA += 1
    else:
        if curA > 1:
            minus += curA - 1
            curA = 0
            curB = 1
        elif curA == 1:
            curA = 0
            curB = 1
        else:
            curB += 1


print(n *(n + 1) // 2 - minus)
'''
6
ABABAB
''' 

import sys
def I():
    return sys.stdin.readline().rstrip()

n = int(I())
s = I()
l = []
cc = 'c'
for c in s:
    if c == cc:
        l[-1] += 1
    else:
        l.append(1)
    cc = c

ans = ( n * (n - 1) ) // 2
for i in range(len(l)):
    if i > 0:
        ans -= l[ i ] - 1
    if i < len(l) - 1:
        ans -= l[ i ]

print( ans )


n = int(input())
if n == 1:
    print(0)
    return
s = input()
K = []
lc = s[0]
cnt = 0
for i in s:
    if i == lc:
        cnt += 1
    else:
        K.append(cnt)
        cnt = 1
    lc = i
K.append(cnt)
bad = 3 * n - K[0] - K[-1] - (len(K) - 1)
print(n * (n + 1) // 2 - bad)


import sys
readline = sys.stdin.readline
N = int(readline())
S = [1 if s == 'A' else 0 for s in readline().strip()]
ans = 0
L1 = [None]*(N+1)
L2 = [None]*(N+1)
for i in range(N-1, -1, -1):
    s = S[i]
    L1[i] = L1[i+1]
    L2[i] = L2[i+1]
    if s == 1:
        L1[i] = i
    else:
        L2[i] = i
    
for i in range(N-1):
    s = S[i]
    sn = S[i+1]
    if s == sn:
        if s == 1:
            if L2[i] is not None:
                ans -= 1
        else:
            if L1[i] is not None:
                ans -= 1
    else:
        if s == 1:
            if L1[i+1] is None:
                ans -= N-i-1
            else:
                ans -= L1[i+1] - (i+1)
        else:
            if L2[i+1] is None:
                ans -= N-i-1
            else:
                ans -= L2[i+1] - (i+1)
print((N-1)*N//2+ans)  

import itertools

n = int(input())

s = input()
x = []

for k, g in itertools.groupby(s):
	l = len(list(g))
	x += [l]

bad = 0
for f, g in zip(x, x[1:]):
	bad += f + g - 1

good = n * (n+1)//2-n-bad

print(good)


n=int(input())
s=input()
x=s[0]
l=1
r=0
for i in range(1,n):
    y=s[i]
    if x==y:
        r+=i
        if l<i:
            r-=1
        l+=1
    else:
        r+=i-l
        l=1
    x=y
print(r)


def comp(a):
	if a=="A":
		return "B"
	else:
		return "A"

n=int(input())
s=input()
ans=(n*(n-1))//2
groups=[0]
prev=s[0]
for i in range(1,n):
	if s[i]!=prev:
		groups.append(i)
		prev=s[i]
for i in range(0,len(groups)-2):
	ans -= (groups[i+2]-groups[i]-1)
if len(groups)>1:
	ans -= (n-groups[-2]-1)
print (ans)

import sys
import math
from collections import defaultdict
from itertools import combinations
from itertools import permutations
input = lambda : sys.stdin.readline().rstrip()
read = lambda : list(map(int, input().split()))
def write(*args, sep="\n"):
  for i in args:
    sys.stdout.write("{}".format(i) + sep)
INF = float('inf')
MOD = int(1e9 + 7)

n = int(input())
s = input() 
arr = [[s[0], 1]]

for i in s[1:]:
  if i == arr[-1][0]:
    arr[-1][1] += 1
  else:
    arr.append([i, 1])

ans = (n) * (n - 1) // 2 

if len(arr) == 1:
  print(ans)
  return

elif len(arr) == 2:
  ans -= arr[0][1]
  ans -= arr[1][1]
  print(ans + 1)
  return

else:
  #print(arr)
  ans -= arr[1][1]
  ans -= arr[-2][1]
  for i in range(1, len(arr) - 1):
    ans -= arr[i - 1][1]
    ans -= arr[i + 1][1]
    ans += 1
  print(ans + 1)
  


#n, m = map(int, input().split())
n = int(input())

s = input()

ans = int(n * (n - 1) / 2)
c = 0

for i in range(n):
    if s[i] == 'A':
        c += 1
    else:
        if c > 1:
            ans -= (c - 1)
        c = 0
c = 0

for i in range(n):
    if s[i] == 'B':
        c += 1
    else:
        if c > 1:
            ans -= (c - 1)
        c = 0

s = s[::-1]

c = 0
for i in range(n):
    if s[i] == 'A':
        c += 1
    else:
        if c > 1:
            ans -= (c - 1)
        c = 0
c = 0

for i in range(n):
    if s[i] == 'B':
        c += 1
    else:
        if c > 1:
            ans -= (c - 1)
        c = 0
c = 0

if s[0] == 'A':
    c += 1
for i in range(n):
    if s[i] == 'A':
        c += 1
    elif c >= 1:
        ans -= 1
        c = 0

c = 0
if s[0] == 'B':
    c += 1
for i in range(n):
    if s[i] == 'B':
        c += 1
    elif c >= 1:
        ans -= 1
        c = 0

print(ans)

n = int(input())
s = input()
arr = []
for i in range(n):
    c = 0 if s[i] == 'A' else 1
    if not arr or arr[-1][0] != c:
        arr.append([c, 1])
    else:
        arr[-1][1] += 1
cnt = (n * n + n) // 2
if len(arr) == 1:
    print(cnt - n)
    return
for i in range(0, len(arr)):
    cnt -= arr[i][1] + (arr[i][1] if i != 0 and i != len(arr) - 1 else 0)
print(cnt - n + len(arr) - 1)

from sys import stdin,stdout
n=int(stdin.readline().strip())
s=stdin.readline().strip()
acumA=[0 for i in range(n+3)]
acumB=[0 for i in range(n+3)]
dictA=[-1 for i in range(n+3)]
dictB=[-1 for i in range(n+3)]
for i in range(n):
    if i!=0:
        acumA[i]+=acumA[i-1]
        acumB[i]+=acumB[i-1]
    if s[i]=="A":
        acumA[i]+=1
        dictA[acumA[i]]=i
    
    if s[i]=="B":
        acumB[i]+=1
        dictB[acumB[i]]=i
ans=0
for i in range(n-1):
    if s[i]=="A":
        if(dictA[acumA[i]+1]==-1):
            continue
        x=dictB[acumB[i]+1]
        if(x==-1):
            x=n
        ans+=(x-i-1)
        x=dictB[acumB[i]+1]
        if(x==-1):
            continue
        x=max(dictB[acumB[i]+1],dictA[acumA[i]+1]-1)

        ans+=(n-x-1)
    else:
        if(dictB[acumB[i]+1]==-1):
            continue
        x=dictA[acumA[i]+1]
        if(x==-1):
            x=n
        ans+=(x-i-1)
        x=dictA[acumA[i]+1]
        if(x==-1):
            continue
        x=max(dictA[acumA[i]+1],dictB[acumB[i]+1]-1)
        ans+=(n-x-1)
print(ans)


import sys
import math
input = sys.stdin.readline

n=int(input())
s=input()
count=-s.count("AB")-s.count("BA")
s=list(s)
arr1=[-1]
arr2=[-1]
for i in range(n):
    if s[i]=="A":
        arr1.append(i)
    else:
        arr2.append(i)

arr1.append(n)
arr2.append(n)
#print(count)
for i in range(1,len(arr1)-1):
    count+=arr1[i]-arr1[i-1]-1
#print(count)
for i in range(1,len(arr2)-1):
    count+=arr2[i]-arr2[i-1]-1
#print(count)
for i in range(1,len(arr1)-1):
    count+=arr1[i+1]-arr1[i]-1
#print(count)
for i in range(1,len(arr2)-1):
    count+=arr2[i+1]-arr2[i]-1
#print(count)
print(n*(n-1)//2-count)

n=int(input())
a=list(input())
A=B=-1
index=[0]*n
arr=0
is_a=-1
is_b=-1
for i in range(n-1,-1,-1):
    if a[i]=='A':
        index[i]=A
        if A==-1:
            is_a=i
        A=i
    else:
        index[i]=B
        if B==-1:
            is_b=i
        B=i
for i in range(n):
    if index[i]-1==i:
        if a[i]=='A':
            if is_b>=i:
                arr-=1
        else:
            if is_a>=i:
                arr-=1
    if index[i]!=-1:
        arr+=n-index[i]
            
print(arr)


from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
#ts=time.time()
#sys.setrecursionlimit(10**6)
#input=sys.stdin.readline
show_flg=False
#show_flg=True


def solve(s):
    ans=0
    n=len(s)
    show(*s,n*(n-1)//2)
    t=[]
    if n==1:
        print(0)
        return
    if len(Counter(s))==1:
        print(n*(n-1)//2)
        return
    p=s[0]
    c=1
    
    for i in range(1,n):
        if s[i]==p:
            c+=1
        else:
            ans+=c
            p=s[i]
            t.append(c)
            c=1
        show('i,ans,c,p',i,ans,c,p)
    t.append(c)
    ans=0
    for i in range(len(t)-1):
        ans+=t[i]+t[i+1]-1
    show(ans,t)
    print(n*(n-1)//2-(ans))
    return ans
   
q=1
for _ in range(q):
    n=I()
    s=list(input())
    #s=[chr(random.randint(1,2)+96-32) for i in range(random.randint(1,6))]
    solve(s)




n = int(input())
s = input()

prev_b = -1
prev_a = -1
ans = 0
for i in range(n):
    if s[i] == "B":
        ans += prev_b + 1
        if prev_b + 1 == i and prev_a != -1:
            ans -= 1
        prev_b = i 
        
    else:
        ans += prev_a + 1
        if prev_a + 1 == i and prev_b != -1:
            ans -= 1
        prev_a = i
print(ans)

n = int(input())
s = input().rstrip()
s += "#"
ans = (n - 1) * n // 2
if "A" not in s or "B" not in s:
    print(ans)
    return

cnt = 0
counts = []
for i, ch in enumerate(s):
    if i == 0:
        prev = ch
        cnt += 1
        continue
    if prev == ch:
        cnt += 1
    else:
        counts.append(cnt)
        cnt = 1
    prev = ch

for c1, c2 in zip(counts, counts[1:]):
    ans -= c1 + c2 - 1
print(ans)

# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
S = input()

total = (N+1)*N // 2
ans = total - N

L = []
cnt = 1
for i in range(1, N):
    if S[i-1] == S[i]:
        cnt += 1
    else:
        L.append(cnt)
        cnt = 1
R = []
cnt = 1
for i in range(N-2, -1, -1):
    if S[i+1] == S[i]:
        cnt += 1
    else:
        R.append(cnt)
        cnt = 1

ans -= sum(L) + sum(R) - len(L)
print(ans)


import sys
input = sys.stdin.readline

n=int(input())
S=input().strip()

A=[]
B=[]

for i in range(n):
    if S[i]=="A":
        A.append(i)
    else:
        B.append(i)

BE=[-1]*n

for i in range(1,len(A)):
    BE[A[i]]=A[i-1]

for i in range(1,len(B)):
    BE[B[i]]=B[i-1]


LEN=n+10
BIT=[0]*(LEN+1)

def update(v,w):
    while v<=LEN:
        BIT[v]+=w
        v+=(v&(-v))

def getvalue(v):
    ANS=0
    while v!=0:
        ANS+=BIT[v]
        v-=(v&(-v))
    return ANS

ANS=0

for i in range(n):
    
    if BE[i]!=-1:
        update(BE[i]+1,1)
        ANS+=getvalue(BE[i]+1)

    #print(i,ANS)

print(ANS)




    


import sys
import itertools
import math
import collections
from collections import Counter

#########################
# imgur.com/Pkt7iIf.png #
#########################

def pow(x, y, mod):
    r = 1
    x = x % mod
    while y > 0:
        if y & 1:
            r = (r * x) % mod
        y = y >> 1
        x = (x * x) % mod
    return r
def sieve(n):
    prime = [True for i in range(n + 1)]
    p = 2
    while (p * p <= n):
        if (prime[p] == True):
            for i in range(p * 2, n + 1, p):
                prime[i] = False
        p += 1
    prime[0] = prime[1] = False
    r = [p for p in range(n + 1) if prime[p]]
    return r
def divs(n, start = 1):
    r = []
    for i in range(start, int(math.sqrt(n) + 1)):
        if (n % i == 0):
            if (n / i == i):
                r.append(i)
            else:
                r.extend([i, n // i])
    return r
def cdiv(n, k): return n // k + (n % k != 0)
def ii(): return int(input())
def mi(): return list(map(int, input().split()))
def li(): return list(map(int, input().split()))
def lcm(a, b): return abs(a * b) // math.gcd(a, b)
def prr(a, sep = ' '): print(sep.join(map(str, a)))
def dd(): return collections.defaultdict(int)

n = ii()
s = input()
used = [set() for i in range(n)]
i = 0
res = 0
while i < n - 1:
    if s[i] != s[i + 1]:
        j = i + 1
        while j < n and s[j] != s[i]:
            used[i].add(j)
            res += 1
            j += 1
        i = j - 1
        continue
    i += 1

i = n - 1
while i > 1:
    if s[i] != s[i - 1]:
        j = i - 1
        while j >= 0 and s[j] != s[i]:
            if i not in used[j]:
                res += 1
            j -= 1
        i = j + 1
        continue
    i -= 1

print((n*(n-1))//2 - res)





















import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
s = input()[:-1]

ans = 0

i = 0
arr = [0]
prefix = [0,0]
while i < len(s):
    n = s[i]
    cnt = 0
    while i < len(s) and n == s[i]:
        cnt+=1
        i+=1
    arr.append(cnt)
    prefix.append(prefix[-1]+cnt)
    
ans = 0
#print(prefix)
for i in range(len(arr)-1):
    #print(arr[i+1], prefix[i], prefix[i+1])
    ans+=arr[i+1]*prefix[i+1]
    #print(ans, end = " ")
    ans-=arr[i]
    if prefix[i+1] > 0:
        ans-=(arr[i+1]-1)
    ans += ((arr[i+1]*(arr[i+1]-1))//2)
    #print(ans)
print(ans)








n = int(input())
s = input()

def bin_sear_pos(j, arr):
	initial = 0
	final = len(arr)-1
	middle = (initial+final)//2
	if arr[final] <= j:
		return final+1
	elif arr[initial]>j:
		return initial
	while arr[middle] != j and (arr[middle]>j or arr[middle+1]<=j) :
		if arr[middle]<j:
			initial = middle
			middle = (initial+final)//2
		else:
			final = middle
			middle = (initial+final)//2

	return middle+1


count_a = 0
count_b = 0
dic = {0:[], 1:[]}
for i in range(n):
	if s[i] =="A":
		count_a += 1
		dic[0].append(i)
	else:
		count_b += 1
		dic[1].append(i)

count = 0
count += count_a*(count_a-1)//2
count += count_b*(count_b-1)//2
if count_a !=0 and count_b !=0:
	for i in range(len(dic[0])-1):
		#print("IN")
		b_pos = bin_sear_pos(dic[0][i], dic[1])

		#print(b_pos)
		if b_pos<len(dic[1]):
			count += len(dic[1]) - bin_sear_pos(max(dic[0][i+1], dic[1][b_pos]), dic[1])
		#print(count)

	for i in range(len(dic[1])-1):
		a_pos = bin_sear_pos(dic[1][i], dic[0])
		if a_pos < len(dic[0]):
			count += len(dic[0]) - bin_sear_pos(max(dic[1][i+1], dic[0][a_pos]), dic[0])


print(count)

from math import *
n = int(input())
s = list(input())
ct = 1
prev = 1
s1 = 0
a = []
for i in range(1,n):
	if(s[i] != s[i-1]):
		a.append(ct)
		#s1 += 1 - ct - prev
		prev = ct
		ct = 1
	else:
		ct += 1
a.append(ct)

#print(s1,a)
s2 = 0
for i in range(0,len(a)):
	s1 -= 2*a[i]
	s1 -= a[i]/2
	s2 += a[i]
s1 += s2*s2/2
s1 += len(a)-1+a[0]+a[-1]
print(int(s1))


n=int(input())
a=list(input())
ans=n*(n-1)//2
l=1
for itr in range(1,n):
    #print(ans)
    if a[itr]==a[itr-1]: l+=1
    else: 
        ans-=l
        l=1
l=1
a=a[::-1]
for itr in range(1,n):
    if a[itr]==a[itr-1]: l+=1
    else: 
        ans-=l-1
        l=1
print(ans)

n = int(input())
s = input()

ans = n*(n+1)/2 - n

count,i = 0,0
l = list()

while(i<n):
	c = s[i]
	val = 0
	while(i<n and s[i] == c):
		i+=1
		val += 1
	l.append(val)

count += len(l)-1
l = list(map(list, list(zip(l,l[1:]))))
for a,b in l:
	count += a-1 + b-1

print(int(ans - count))