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: HARD
Tags: String algorithms

Sorting

Combinatorics

Dynamic programming
Skill types: Dynamic programming

Sorting

Starter code:

Solutions:
def main():
	n = int(input())
	s = input()
	ret = n * (n - 1) // 2
	for x in range(2):
		cur = 1
		for i in range(1, n):
			if s[i - 1] == s[i]:
				cur += 1
			else:
				ret -= cur - x
				cur = 1
		s = s[::-1]
	return ret
print(main())


n = int(input())
S = input()
pa = -1
pb = -1
cnt = 0
for (i, s) in enumerate(S):
	if s == 'A':
		if pa == -1:
			pa = i
		else:
			cnt += pa + 1
			if S[i - 1] == 'A' and pb != -1:
				cnt -= 1
			pa = i
	if s == 'B':
		if pb == -1:
			pb = i
		else:
			cnt += pb + 1
			if S[i - 1] == 'B' and pa != -1:
				cnt -= 1
			pb = i
print(cnt)


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)


n = int(input())
a = list(input())
ans = n * (n - 1) // 2
l = 1
for itr in range(1, n):
	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)


X = input()
X = input()
(a, b, c, d, k) = (0, 0, 1, 1, 1)
l = len(X)
for i in range(1, l):
	if X[i] == X[i - 1]:
		if c != 1:
			c += 1
			b += 1
		else:
			c += 1
			b += d
	else:
		if c != 1:
			b += 2 - c - k
			d = c
			c = 1
		else:
			b += d - k
			d = 1
			c = 1
		k = 0
	a += b
print(a)


n = int(input())
s = input()
ans = n * (n - 1) // 2
cnt = 1
for i in range(1, len(s)):
	if s[i] == s[i - 1]:
		cnt += 1
	else:
		ans -= cnt
		cnt = 1
cnt = 0
for i in range(len(s) - 2, -1, -1):
	if s[i] == s[i + 1]:
		cnt += 1
	else:
		ans -= cnt
		cnt = 0
print(ans)


import sys
input = sys.stdin.readline
n = int(input())
s = input()
res = n * (n - 1) // 2
for x in range(2):
	cur = 1
	for i in range(1, n):
		if s[i] == s[i - 1]:
			cur += 1
		else:
			res -= cur - x
			cur = 1
	s = s[::-1][1:]
print(res)


n = int(input())
s = input()
res = n * (n - 1) // 2
cur = 1
for i in range(1, n):
	if s[i] == s[i - 1]:
		cur += 1
	else:
		res -= cur
		cur = 1
s = s[::-1]
cur = 0
for i in range(1, n):
	if s[i] == s[i - 1]:
		cur += 1
	else:
		res -= cur
		cur = 0
print(res)


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)


from bisect import *
n = int(input())
s = input()
if s in ['A' * n, 'B' * n]:
	print(n * (n - 1) // 2)
	exit()
(A_idx, B_idx) = ([], [])
for i in range(n):
	if s[i] == 'A':
		A_idx.append(i)
	else:
		B_idx.append(i)
ans = 0
for i in range(n - 1):
	if s[i:i + 2] == 'AA':
		if i < B_idx[-1]:
			ans += n - i - 2
		else:
			ans += n - i - 1
	elif s[i:i + 2] == 'AB':
		if i == A_idx[-1]:
			continue
		mark = bisect_left(A_idx, i)
		ans += n - A_idx[mark + 1]
	elif s[i:i + 2] == 'BB':
		if i < A_idx[-1]:
			ans += n - i - 2
		else:
			ans += n - i - 1
	else:
		if i == B_idx[-1]:
			continue
		mark = bisect_left(B_idx, i)
		ans += n - B_idx[mark + 1]
print(ans)


n = int(input())
s = input()
cnt = n
for x in range(2):
	cur = 1
	for i in range(1, n):
		if s[i] == s[i - 1]:
			cur += 1
		else:
			cnt += cur - x
			cur = 1
	s = s[::-1]
print(n * (n + 1) // 2 - cnt)


n = int(input())
s = list(input())
tot = n * (n - 1) // 2
for x in range(2):
	cur = 1
	for i in range(1, n):
		if s[i] == s[i - 1]:
			cur += 1
		else:
			tot -= cur - x
			cur = 1
	s = s[::-1]
print(tot)


n = int(input())
if n == 1:
	print(0)
	exit(0)
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)


n = int(input())
s = input()
ans = n * (n - 1) // 2
same = 1
for i in range(1, n):
	if s[i] == s[i - 1]:
		same += 1
	else:
		ans -= same
		same = 1
same = 1
for i in range(n - 2, -1, -1):
	if s[i] == s[i + 1]:
		same += 1
	else:
		ans -= same - 1
		same = 1
print(ans)


n = int(input())
st = input() + 'C'
add = 1
sum = []
count = 0
for i in range(n):
	if st[i] == st[i + 1]:
		add += 1
	else:
		sum.append(add)
		add = 1
		count += 1
final = [0 for i in range(count + 1)]
i = count - 1
pre = 0
while i >= 0:
	pre += sum[i]
	final[i] = pre
	i -= 1
ans = 0
for i in range(count - 1):
	for j in range(sum[i], 0, -1):
		ans += j - 1
		if j > 1:
			ans += final[i + 1] - 1
		else:
			ans += final[i + 2]
ans += sum[count - 1] * (sum[count - 1] - 1) // 2
print(ans)


n = int(input())
s = list(map(str, input().strip()))
cnta = 0
cntb = 0
ans = 0
for (i, v) in enumerate(s):
	if v == 'A':
		ans += cnta - (cntb and cntb < cnta)
		cnta = i + 1
	else:
		ans += cntb - (cnta and cnta < cntb)
		cntb = i + 1
print(ans)


from collections import defaultdict

class Bit:

	def __init__(self, n):
		self.size = n
		self.tree = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.size:
			self.tree[i] += x
			i += i & -i
n = int(input())
s = input()
st = []
dc = defaultdict(int)
for i in range(n):
	if dc[s[i]]:
		st.append((dc[s[i]], i + 1))
	dc[s[i]] = i + 1
ln = len(st)
st.sort()
ans = 0
cnt = 0
bit = Bit(n + 2)
for i in range(ln):
	(l, r) = st[i]
	bit.add(1, 1)
	bit.add(r + 1, -1)
for i in range(ln):
	ans += bit.sum(st[i][1])
	bit.add(1, -1)
	bit.add(st[i][1] + 1, 1)
print(ans)


(n, s) = (int(input()), input())
r = n * (n - 1) // 2
for j in range(2):
	e = 1
	for i in range(1, n):
		if s[i - 1] == s[i]:
			e += 1
		else:
			r -= e - j
			e = 1
	s = s[::-1]
print(r)


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())
tt = n * (n - 1) // 2
s = input().lower()
ss = 0
for i in range(0, n):
	if s[i] == 'a':
		j = i - 1
		while j > -1 and s[j] == 'b':
			ss += 1
			j -= 1
		j = i + 1
		while j < n and s[j] == 'b':
			ss += 1
			j += 1
for i in range(0, n):
	if s[i] == 'b':
		j = i - 1
		while j > -1 and s[j] == 'a':
			ss += 1
			j -= 1
		j = i + 1
		while j < n and s[j] == 'a':
			ss += 1
			j += 1
print(tt - ss + s.count('ab') + s.count('ba'))


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)


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

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 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)


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
		elif is_a >= i:
			arr -= 1
	if index[i] != -1:
		arr += n - index[i]
print(arr)


from sys import stdin, setrecursionlimit
setrecursionlimit(10 ** 7)

def iin():
	return int(stdin.readline())

def lin():
	return list(map(int, stdin.readline().split()))

def main():
	n = iin()
	s = list(input())
	ans = n * (n - 1) // 2
	for i in range(2):
		ch = 1
		for j in range(1, n):
			if s[j] == s[j - 1]:
				ch += 1
			else:
				ans -= ch - i
				ch = 1
		s = s[::-1]
	print(ans)
main()


import os, sys
from io import BytesIO
n = int(input())
s = input()
a = [1]
for i in range(1, n):
	if s[i] == s[i - 1]:
		a[-1] += 1
	else:
		a.append(1)
ans = n * (n - 1) // 2 + a[0] - 1 + a[-1]
for i in range(len(a)):
	ans -= 2 * a[i] - 1
print(ans)


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)


n = int(input())
x = str(input())
count = 1
ans = n * (n - 1) / 2
dp = []
for i in range(1, n):
	if x[i] == x[i - 1]:
		count += 1
	if x[i] != x[i - 1]:
		dp.append(count)
		count = 1
	if i == n - 1:
		dp.append(count)
for i in range(len(dp)):
	if len(dp) == 1:
		pass
	elif i == 0:
		ans -= dp[i + 1]
	elif i == len(dp) - 1:
		ans -= dp[i - 1]
	else:
		ans -= dp[i - 1] + dp[i + 1]
print(int(ans + len(dp) - 1))


n = int(input())
s = input()
blocks = 1
first = 1
last = 1
while first < n and s[first] == s[first - 1]:
	first += 1
while last < n and s[-last - 1] == s[-last]:
	last += 1
for i in range(1, n):
	if s[i] != s[i - 1]:
		blocks += 1
print(n * (n - 1) // 2 - (2 * n + 1 - first - last - blocks))


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))


n = int(input())
s = input()
gh = 1
cn = s[0]
cvb = 0
for i in range(1, n):
	if s[i] != cn:
		cvb += gh
		gh = 1
	else:
		gh += 1
	cn = s[i]
gh = 1
s = list(reversed(s))
cn = s[0]
for i in range(1, n):
	if s[i] != cn:
		cvb += gh
		gh = 1
	else:
		gh += 1
	cn = s[i]
for i in range(n - 1):
	if s[i] != s[i + 1]:
		cvb -= 1
print(n * (n - 1) // 2 - cvb)


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)
	exit()
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)


import os, sys
from io import BytesIO, IOBase
from bisect import bisect

def main():
	n = int(input())
	s = input().strip()
	ls = [[], []]
	for i in range(n):
		if s[i] == 'A':
			ls[0].append(i)
		else:
			ls[1].append(i)
	ls[0].append(n)
	ls[1].append(n)
	ans = 0
	for i in range(n):
		if s[i] == 'A':
			x = bisect(ls[1], i)
			y = bisect(ls[0], i + 1)
			if x != len(ls[1]) and ls[1][x] == i + 1 and (y != len(ls[0])):
				ans += max(0, n - ls[0][y])
			elif x != len(ls[1]):
				ans += max(0, n - ls[1][x] - 1)
				ans += max(0, ls[1][x] - i - 1)
		else:
			x = bisect(ls[0], i)
			y = bisect(ls[1], i + 1)
			if y != len(ls[0]) and ls[0][x] == i + 1 and (y != len(ls[1])):
				ans += max(0, n - ls[1][y])
			elif x != len(ls[0]):
				ans += max(0, n - ls[0][x] - 1)
				ans += max(0, ls[0][x] - i - 1)
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
input = sys.stdin.readline
n = int(input())
s = input().rstrip()
cnt = 0
for rep in range(2):
	cur = 1
	for i in range(1, n):
		if s[i] == s[i - 1]:
			cur += 1
		else:
			cnt += cur - rep
			cur = 1
	s = s[::-1]
print(n * (n - 1) // 2 - cnt)


n = int(input())
inp = input()
ans = n * (n - 1) // 2
for rev in range(2):
	cur = 1
	for i in range(1, n):
		if inp[i - 1] == inp[i]:
			cur += 1
		else:
			ans -= cur - rev
			cur = 1
	inp = inp[::-1]
print(ans)


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
		elif L1[i] is not None:
			ans -= 1
	elif s == 1:
		if L1[i + 1] is None:
			ans -= N - i - 1
		else:
			ans -= L1[i + 1] - (i + 1)
	elif L2[i + 1] is None:
		ans -= N - i - 1
	else:
		ans -= L2[i + 1] - (i + 1)
print((N - 1) * N // 2 + ans)


import sys, atexit
from io import BytesIO
inp = BytesIO(sys.stdin.buffer.read())
input = lambda : inp.readline().decode('ascii')
buf = BytesIO()
atexit.register(lambda : sys.__stdout__.buffer.write(buf.getvalue()))
n = int(input())
t = input().strip()
ans = n * (n - 1) // 2
for x in range(2):
	cnt = 1
	for i in range(n - 1):
		if t[i] == t[i + 1]:
			cnt += 1
		else:
			ans -= cnt - x
			cnt = 1
	t = t[::-1]
print(ans)


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())
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
for i in range(1, len(l)):
	count += l[i] - 1 + l[i - 1] - 1
print(int(ans - count))


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=-10 ** 6, func=lambda a, b: max(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=10 ** 6, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353
prime = [True for i in range(50001)]
pp = []

def SieveOfEratosthenes(n=50000):
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for i in range(50001):
		if prime[i]:
			pp.append(i)
n = int(input())
s = list(input())
prea = [0] * n
preb = [0] * n
posta = [0] * n
postb = [0] * n
(a, b) = (0, 0)
for i in range(n):
	prea[i] = max(0, a - 1)
	preb[i] = max(0, b - 1)
	if s[i] == 'A':
		a += 1
		b = 0
	else:
		b += 1
		a = 0
(a, b) = (0, 0)
for i in range(n - 1, -1, -1):
	posta[i] = a
	postb[i] = b
	if s[i] == 'A':
		a += 1
		b = 0
	else:
		b += 1
		a = 0
ct = 0
res = n * (n + 1) // 2
for i in range(n):
	if s[i] == 'A':
		ct += preb[i] + postb[i] + 1
	else:
		ct += prea[i] + posta[i] + 1
res -= ct
print(res)


import sys
import math
from collections import defaultdict
n = int(sys.stdin.readline())
s = list(sys.stdin.readline()[:-1])
count = 0
ans = n * (n - 1) // 2
for x in range(2):
	count = 1
	for i in range(1, n):
		if s[i] == s[i - 1]:
			count += 1
		else:
			ans -= count - x
			count = 1
	s = s[::-1]
print(ans)


from sys import stdin
n = int(input())
s = stdin.read(n)
ans = n * (n - 1) // 2
k = 0
m = 0
for i in range(1, n):
	p = s[i - 1]
	t = s[i]
	if p == t:
		k += 1
	else:
		ans -= k * (1 << m) + 1
		m |= 1
		k = 0
else:
	ans -= k * m
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):
		b_pos = bin_sear_pos(dic[0][i], dic[1])
		if b_pos < len(dic[1]):
			count += len(dic[1]) - bin_sear_pos(max(dic[0][i + 1], dic[1][b_pos]), dic[1])
	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)


def main():
	import sys
	input = sys.stdin.readline

	class UnionFind:

		def __init__(self, n):
			self.n = n
			self.root = [-1] * (n + 1)
			self.rnk = [0] * (n + 1)

		def find_root(self, x):
			if self.root[x] < 0:
				return x
			else:
				self.root[x] = self.find_root(self.root[x])
				return self.root[x]

		def unite(self, x, y):
			x = self.find_root(x)
			y = self.find_root(y)
			if x == y:
				return
			elif self.rnk[x] > self.rnk[y]:
				self.root[x] += self.root[y]
				self.root[y] = x
			else:
				self.root[y] += self.root[x]
				self.root[x] = y
				if self.rnk[x] == self.rnk[y]:
					self.rnk[y] += 1

		def isSameGroup(self, x, y):
			return self.find_root(x) == self.find_root(y)

		def size(self, x):
			return -self.root[self.find_root(x)]
	N = int(input())
	s = input().rstrip('\n')
	UF = UnionFind(N + 1)
	for i in range(N - 1):
		if s[i] == s[i + 1]:
			UF.unite(i + 1, i + 2)
	ans = N * (N - 1) // 2
	for i in range(N - 1):
		if s[i] != s[i + 1]:
			ans -= UF.size(i + 1) + UF.size(i + 2) - 1
	print(ans)
main()


length = int(input())
s = input()
substrings = sum(range(length + 1))
substrings -= length
transitioned = False
journey = 0
i = 0
current_character = s[i]
journey += 1
i += 1
while i < length:
	if s[i] == current_character:
		journey += 1
	else:
		if journey > 1:
			if i == journey:
				substrings -= journey - 1
			else:
				substrings -= 2 * journey - 2
		substrings -= 1
		transitioned = True
		journey = 1
	current_character = s[i]
	i += 1
if journey > 1 and transitioned:
	substrings -= journey - 1
print(substrings)


import os
n = int(input())
s = input()
res = n * (n - 1) // 2
for tmp in range(2):
	cur = 1
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			cur += 1
		else:
			res -= cur - tmp
			cur = 1
	s = s[::-1]
print(res)


import os
from itertools import combinations
import math
lenght = int(input())
st = input()
res = lenght * (lenght - 1) / 2
for x in range(2):
	cur = 1
	for i in range(1, lenght):
		if st[i] == st[i - 1]:
			cur += 1
		else:
			res -= cur - x
			cur = 1
	st = st[::-1]
print(int(res))


from sys import stdin
from array import array
input = stdin.readline
n = int(input())
s = input().strip('\n')
ans = (n ** 2 - n) // 2
p = s[0]
k = array('l')
b = 0
for c in s + '_':
	if c != p:
		k.append(b)
		p = c
		b = 1
	else:
		b += 1
for i in range(len(k)):
	if i != 0:
		ans -= k[i - 1]
	if i != len(k) - 1:
		ans -= k[i + 1]
ans += len(k) - 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(1000000000.0 + 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:
	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)


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
for i in range(len(arr) - 1):
	ans += arr[i + 1] * prefix[i + 1]
	ans -= arr[i]
	if prefix[i + 1] > 0:
		ans -= arr[i + 1] - 1
	ans += arr[i + 1] * (arr[i + 1] - 1) // 2
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)
	exit()
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)


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)


def main():
	n = int(input())
	s = input()
	groupSizes = []
	sz = 0
	for i in range(n):
		if i - 1 >= 0 and s[i] != s[i - 1]:
			groupSizes.append(sz)
			sz = 0
		sz += 1
	groupSizes.append(sz)
	badCnts = 0
	m = len(groupSizes)
	for i in range(m):
		if i + 1 < m:
			badCnts += groupSizes[i + 1]
		if i - 1 >= 0:
			badCnts += groupSizes[i - 1]
	badCnts -= m - 1
	ans = n * (n - 1) // 2 - badCnts
	print(ans)
	return
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(x, y):
	print('? {} {}'.format(x, y))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(ans))
	sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
for _abc in range(1):
	main()


from itertools import groupby
n = int(input())
a = [len(list(v)) for (k, v) in groupby(input())]
ans = n * (n - 1) // 2
for (x, y) in zip(a, a[1:]):
	ans -= x + y - 1
print(ans)


import sys
n = int(sys.stdin.readline())
s = list(sys.stdin.readline()[:-1])
ans = n * (n - 1) // 2
for x in range(2):
	count = 1
	for i in range(1, n):
		if s[i] == s[i - 1]:
			count += 1
		else:
			ans -= count - x
			count = 1
	s = s[::-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)
for i in range(1, len(arr1) - 1):
	count += arr1[i] - arr1[i - 1] - 1
for i in range(1, len(arr2) - 1):
	count += arr2[i] - arr2[i - 1] - 1
for i in range(1, len(arr1) - 1):
	count += arr1[i + 1] - arr1[i] - 1
for i in range(1, len(arr2) - 1):
	count += arr2[i + 1] - arr2[i] - 1
print(n * (n - 1) // 2 - count)


import sys, os, io
n = int(input())
s = input()
ans = (n - 1) * n // 2
cnt = 1
for i in range(1, n):
	if s[i] == s[i - 1]:
		cnt += 1
	else:
		ans -= cnt
		cnt = 1
s = s[::-1]
cnt = 1
for i in range(1, n):
	if s[i] == s[i - 1]:
		cnt += 1
	else:
		ans -= cnt - 1
		cnt = 1
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(ANS)


from heapq import heappush, heappop
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations
import sys
import bisect
import string

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')
show_flg = False

def solve(s):
	ans = 0
	n = len(s)
	show(*s, n * (n - 1) // 2)
	t = []
	if n == 1:
		print(0)
		exit()
	if len(Counter(s)) == 1:
		print(n * (n - 1) // 2)
		exit()
	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())
	solve(s)


n = int(input())
s = input()
(a, b, c) = (-1, -1, 0)
for i in range(n):
	if s[i] == 'A':
		c += i - a - 1
		a = i
	else:
		c += i - b - 1
		b = i
t = s[::-1]
(a, b) = (-1, -1)
for i in range(n):
	if t[i] == 'A':
		c += max(0, i - a - 2)
		a = i
	else:
		c += max(0, i - b - 2)
		b = i
print(n * (n - 1) // 2 - c)


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)


def solve():
	n = int(input())
	array = input()
	(i, j) = (0, 0)
	totalBadString = 0
	l = [0, 0]
	l[ord(array[i]) - 65] += 1
	while i < n - 1 and j < n:
		if l[0] == 1 and l[1] >= 1 or (l[1] == 1 and l[0] >= 1):
			if l[0] == 1 and l[1] == 1:
				expectedValue = array[j]
				while array[j] == expectedValue:
					totalBadString += 1
					j += 1
					if j < n:
						l[ord(array[j]) - 65] += 1
					else:
						break
				i += 1
				l[ord(array[i - 1]) - 65] -= 1
			else:
				while l[0] == 1 and l[1] >= 1 or (l[1] == 1 and l[0] >= 1):
					totalBadString += 1
					i += 1
					l[ord(array[i - 1]) - 65] -= 1
				i -= 1
				totalBadString -= 1
				l[ord(array[i]) - 65] += 1
		else:
			j += 1
			if j < n:
				l[ord(array[j]) - 65] += 1
			else:
				break
	print(n * (n - 1) // 2 - totalBadString)
solve()


import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys
from typing import List
N = int(input())
S = input()
ans = N * (N - 1) // 2
for x in range(2):
	cur = 1
	for i in range(1, N):
		if S[i] == S[i - 1]:
			cur += 1
		else:
			ans -= cur - x
			cur = 1
	S = S[::-1]
print(ans)


import sys
from array import array
import typing as Tp

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

def main():
	from itertools import groupby
	n = int(input())
	s = [len(list(val)) * 2 for (key, val) in groupby(input().rstrip())]
	s[0] >>= 1
	s[-1] >>= 1
	ans = n * (n - 1) // 2 - (sum(s) - (len(s) - 1) if len(s) > 1 else 0)
	print(ans)
main()


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)
		prev = ct
		ct = 1
	else:
		ct += 1
a.append(ct)
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))


def solve():
	n = int(input())
	s = input()
	res = n * (n - 1) // 2
	cur = 1
	start = 0
	end = n - 1
	for i in range(1, n):
		if s[i] == s[i - 1]:
			cur += 1
		else:
			res -= cur - 1
			start = i
			cur = 1
			break
	for i in range(n - 2, -1, -1):
		if s[i] == s[i + 1]:
			cur += 1
		else:
			res -= cur - 1
			end = i + 1
			cur = 1
			break
	for i in range(start, end + 1):
		if s[i] == s[i - 1]:
			cur += 1
		else:
			res -= 2 * cur - 1
			cur = 1
	print(res)
solve()


import os
import sys
from io import BytesIO, IOBase
from collections import Counter
import math as mt
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def lcm(a, b):
	return a * b / gcd(a, b)
mod = int(1000000000.0) + 7

def power(k, n):
	if n == 0:
		return 1
	if n % 2:
		return power(k, n - 1) * k
	t = power(k, n // 2)
	return t * t

def totalPrimeFactors(n):
	count = 0
	if n % 2 == 0:
		count += 1
		while n % 2 == 0:
			n //= 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			count += 1
			while n % i == 0:
				n //= i
		i += 2
	if n > 2:
		count += 1
	return count

def main():
	n = int(input())
	S = input()
	s = []
	for i in S:
		if i == 'A' or i == 'B':
			s.append(i)
	aind = [-1]
	bind = [-1]
	for i in range(n):
		if s[i] == 'A':
			aind.append(i)
		else:
			bind.append(i)
	aind.append(n)
	bind.append(n)
	ans = 0
	for i in range(1, len(aind) - 1):
		ans += aind[i + 1] - aind[i] - 1
		ans += aind[i] - aind[i - 1] - 1
	for i in range(1, len(bind) - 1):
		ans += bind[i + 1] - bind[i] - 1
		ans += bind[i] - bind[i - 1] - 1
	for i in range(1, n):
		if s[i] != s[i - 1]:
			ans -= 1
	print(n * (n - 1) // 2 - ans)
	return
main()


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
	elif 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
	elif 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)


n = int(input())
s = input()
ans = n * (n - 1) // 2
cur = 1
for i in range(1, len(s)):
	if s[i] == s[i - 1]:
		cur += 1
	else:
		ans = ans - cur
		cur = 1
s = s[::-1]
cur = 1
for i in range(1, len(s)):
	if s[i] == s[i - 1]:
		cur += 1
	else:
		ans = ans - cur + 1
		cur = 1
print(ans)


n = int(input())
s = input()
ans = n * (n - 1) // 2
l = 1
for i in range(1, n):
	if s[i - 1] == s[i]:
		l += 1
	else:
		ans -= l
		l = 1
l = 1
s = s[::-1]
for i in range(1, n):
	if s[i - 1] == s[i]:
		l += 1
	else:
		ans -= l - 1
		l = 1
print('%d' % ans)


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


p = int(input())
s = input()
i = 0
cnt_Bad = 0
leng = 0
while i < len(s):
	if s[i] == 'A':
		i += 1
		while i < len(s) and s[i] == 'B':
			i += 1
			leng += 1
	else:
		i += 1
cnt_Bad += leng
i = 0
leng = 0
while i < len(s):
	if s[i] == 'B':
		i += 1
		while i < len(s) and s[i] == 'A':
			i += 1
			leng += 1
	else:
		i += 1
cnt_Bad += leng
i = len(s) - 1
leng = 0
while i >= 0:
	if s[i] == 'B':
		i -= 1
		while i >= 0 and s[i] == 'A':
			i -= 1
			leng += 1
	else:
		i -= 1
cnt_Bad += leng
i = len(s) - 1
leng = 0
while i >= 0:
	if s[i] == 'A':
		i -= 1
		while i >= 0 and s[i] == 'B':
			i -= 1
			leng += 1
	else:
		i -= 1
cnt_Bad += leng
i = 0
leng = 0
while i < len(s) - 1:
	if s[i] == 'B' and s[i + 1] == 'A' or (s[i] == 'A' and s[i + 1] == 'B'):
		leng += 1
	i += 1
cnt_Bad -= leng
print((len(s) ** 2 - len(s)) // 2 - cnt_Bad)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import factorial
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 1000000007
INF = float('inf')
from bisect import bisect_left, bisect_right

def main():
	n = N()
	s = input()
	sa = deque()
	sb = deque()
	for i in range(n):
		if s[i] == 'A':
			sa.append(i)
		else:
			sb.append(i)
	res = n * (n - 1) // 2
	la = lb = 0
	for i in range(1, n):
		if s[i - 1] == 'A':
			sa.popleft()
		else:
			sb.popleft()
		if s[i - 1] != s[i]:
			if s[i - 1] == 'A':
				pa = (sa[0] if sa else n) - i
				dif = pa + (i - lb) - 1
				la = i
			else:
				pb = (sb[0] if sb else n) - i
				dif = pb + (i - la) - 1
				lb = i
			res -= dif
	print(res)
main()


n = int(input())
line = input()
left_A = list()
left_A.append(-1)
left_A.append(-1)
left_B = list()
left_B.append(-1)
left_B.append(-1)
counts = list()
i = 0
while i < n:
	counts.append(0)
	i = i + 1
if line[0] == 'A':
	left_A[1] = 0
	i = 1
	if line[1] == line[0]:
		counts[1] = 1
		left_A[0] = left_A[1]
		left_A[1] = 1
	else:
		left_B[1] = 1
else:
	left_B[1] = 0
	i = 1
	if line[1] == line[0]:
		counts[1] = 1
		left_B[0] = left_B[1]
		left_B[1] = 1
	else:
		left_A[1] = 1
i = 2
while i < n:
	if line[i - 1] == line[i]:
		joining = counts[i - 1]
		if line[i] == 'A':
			addiction = 0
			temp_add = left_A[1] - left_A[0] - 2
			if left_A[0] != -1 and temp_add > 0:
				addiction = temp_add
			elif left_A[0] == -1 and i - 1 > 1:
				addiction = i - 1 - 1
			counts[i] = joining + addiction + 1
			left_A[0] = left_A[1]
			left_A[1] = i
		else:
			addiction = 0
			temp_add = left_B[1] - left_B[0] - 2
			if left_B[0] != -1 and temp_add > 0:
				addiction = temp_add
			elif left_B[0] == -1 and i - 1 > 1:
				addiction = i - 1 - 1
			counts[i] = joining + addiction + 1
			left_B[0] = left_B[1]
			left_B[1] = i
	elif line[i] == 'A':
		if left_A[1] >= 0:
			counts[i] = left_A[1] + 1
		left_A[0] = left_A[1]
		left_A[1] = i
	elif line[i] == 'B':
		if left_B[1] >= 0:
			counts[i] = left_B[1] + 1
		left_B[0] = left_B[1]
		left_B[1] = i
	i = i + 1
amount = 0
i = 0
while i < n:
	amount = amount + counts[i]
	i = i + 1
print(amount)


n = int(input())
s = list(input())
u = []
k = 1
for i in range(1, n):
	if s[i] != s[i - 1]:
		u.append(k)
		k = 1
	else:
		k += 1
u.append(k)
ans = n * (n - 1) // 2
for i in range(1, len(u)):
	ans -= u[i - 1]
	ans -= u[i]
	ans += 1
print(ans)


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)


N = int(input())
S = list(input())
pre = S[0]
A = []
a = 0
for s in S:
	if s == pre:
		a += 1
	else:
		A.append(a)
		a = 1
	pre = s
A.append(a)
q = 0
for i in range(len(A) - 1):
	q += A[i] + A[i + 1] - 1
ans = N * (N - 1) // 2 - q
print(ans)


import sys
zz = 1
sys.setrecursionlimit(10 ** 5)
if zz:
	input = sys.stdin.readline
else:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('all.txt', 'w')
di = [[-1, 0], [1, 0], [0, 1], [0, -1]]

def fori(n):
	return [fi() for i in range(n)]

def inc(d, c, x=1):
	d[c] = d[c] + x if c in d else x

def ii():
	return input().rstrip()

def li():
	return [int(xx) for xx in input().split()]

def fli():
	return [float(x) for x in input().split()]

def comp(a, b):
	if a > b:
		return 2
	return 2 if a == b else 0

def gi():
	return [xx for xx in input().split()]

def gtc(tc, ans):
	print('Case #' + str(tc) + ':', ans)

def cil(n, m):
	return n // m + int(n % m > 0)

def fi():
	return int(input())

def pro(a):
	return reduce(lambda a, b: a * b, a)

def swap(a, i, j):
	(a[i], a[j]) = (a[j], a[i])

def si():
	return list(input().rstrip())

def mi():
	return map(int, input().split())

def gh():
	sys.stdout.flush()

def isvalid(i, j, n, m):
	return 0 <= i < n and 0 <= j < m

def bo(i):
	return ord(i) - ord('a')

def graph(n, m):
	for i in range(m):
		(x, y) = mi()
		a[x].append(y)
		a[y].append(x)
t = 1
uu = t
while t > 0:
	t -= 1
	n = fi()
	s = ii()
	d = {}
	ans = c = 0
	for i in range(n):
		if i > 0 and s[i] != s[i - 1]:
			ans += i - d.get(s[i], 0) - 1
			c += 1
		d[s[i]] = i + 1
	d = {}
	s = s[::-1]
	for i in range(n):
		if i > 0 and s[i] != s[i - 1]:
			ans += i - d.get(s[i], 0) - 1
			c += 1
		d[s[i]] = i + 1
	print(n * (n - 1) // 2 - ans - c // 2)


import sys
readline = sys.stdin.readline
read = sys.stdin.read
ns = lambda : readline().rstrip()
ni = lambda : int(readline().rstrip())
nm = lambda : map(int, readline().split())
nl = lambda : list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
	n = ni()
	s = ns() + '$'
	c = n * (n - 1) // 2
	l = list()
	k = s[0]
	t = 0
	for x in s:
		if x == k:
			t += 1
		else:
			l.append(t)
			k = x
			t = 1
	m = len(l)
	for i in range(m - 1):
		(x, y) = (l[i], l[i + 1])
		c -= x + y - 1
	print(c)
	return
solve()


n = int(input())
str = input()
s = n * (n - 1) // 2
nom = 1
for i in range(1, n):
	if str[i] == str[i - 1]:
		nom += 1
	else:
		s -= nom
		nom = 1
nom = 1
str = str[::-1]
for i in range(1, n):
	if str[i] == str[i - 1]:
		nom += 1
	else:
		s -= nom - 1
		nom = 1
print(s)


n = int(input())
s = input()
res = n * (n - 1) // 2
for i in range(2):
	cont = 1
	for a in range(1, n):
		if s[a] == s[a - 1]:
			cont += 1
		else:
			res -= cont - i
			cont = 1
	s = s[::-1]
print(res)