We have a string S of length N consisting of A, T, C, and G.
Strings T_1 and T_2 of the same length are said to be complementary when, for every i (1 \leq i \leq l), the i-th character of T_1 and the i-th character of T_2 are complementary. Here, A and T are complementary to each other, and so are C and G.
Find the number of non-empty contiguous substrings T of S that satisfies the following condition:
 - There exists a string that is a permutation of T and is complementary to T.
Here, we distinguish strings that originate from different positions in S, even if the contents are the same.

-----Constraints-----
 - 1 \leq N \leq 5000
 - S consists of A, T, C, and G.

-----Input-----
Input is given from Standard Input in the following format:
N S

-----Output-----
Print the number of non-empty contiguous substrings T of S that satisfies the condition.

-----Sample Input-----
4 AGCT

-----Sample Output-----
2

The following two substrings satisfy the condition:
 - GC (the 2-nd through 3-rd characters) is complementary to CG, which is a permutation of GC.
 - AGCT (the 1-st through 4-th characters) is complementary to TCGA, which is a permutation of AGCT.

Difficulty: MEDIUM_HARD

Starter code:

Solutions:
import sys
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7

def input():
	return sys.stdin.readline().strip()

def main():
	(N, S) = input().split()
	N = int(N)
	ans = 0
	for i in range(N):
		a = 0
		c = 0
		for j in range(i, N):
			if S[j] == 'A':
				a += 1
			elif S[j] == 'T':
				a -= 1
			elif S[j] == 'C':
				c += 1
			else:
				c -= 1
			if a == c == 0:
				ans += 1
	print(ans)

def __starting_point():
	main()
__starting_point()


(n, s) = input().split()
n = int(n)
cnt = {}
at = 0
gc = 0
ans = 0
cnt[0, 0] = 1
for si in s:
	if si == 'A':
		at += 1
	elif si == 'T':
		at -= 1
	elif si == 'G':
		gc += 1
	else:
		gc -= 1
	if (at, gc) in cnt:
		ans += cnt[at, gc]
		cnt[at, gc] += 1
	else:
		cnt[at, gc] = 1
print(ans)


import sys

def LS():
	return list(sys.stdin.readline().rstrip().split())
(N, S) = LS()
ans = 0
for i in range(int(N)):
	S1 = S[i:]
	(a, g) = (0, 0)
	for s in S1:
		if s == 'A':
			a += 1
		elif s == 'G':
			g += 1
		elif s == 'C':
			g -= 1
		elif s == 'T':
			a -= 1
		if a == g == 0:
			ans += 1
print(ans)


import itertools
(N, S) = input().split()
N = int(N)
AT = [0] * N
CG = [0] * N
for i in range(N):
	if S[i] == 'A':
		AT[i] = 1
	if S[i] == 'T':
		AT[i] = -1
	if S[i] == 'C':
		CG[i] = 1
	if S[i] == 'G':
		CG[i] = -1
AT = [0] + AT
CG = [0] + CG
ATC = list(itertools.accumulate(AT))
CGC = list(itertools.accumulate(CG))
ans = 0
for i in range(N):
	for j in range(i + 1, N):
		if ATC[i] == ATC[j + 1] and CGC[i] == CGC[j + 1]:
			ans += 1
print(ans)


def main():
	(n, s) = input().split()
	ans = 0
	for i in range(int(n)):
		at_cnt = 0
		gc_cnt = 0
		for si in s[i:int(n)]:
			if si == 'A':
				at_cnt += 1
			elif si == 'T':
				at_cnt -= 1
			elif si == 'C':
				gc_cnt += 1
			elif si == 'G':
				gc_cnt -= 1
			if at_cnt == 0 and gc_cnt == 0:
				ans += 1
	print(ans)

def __starting_point():
	main()
__starting_point()


(n, s) = input().split()
N = int(n)
S = list(s)
A = [0 for _ in range(N)]
G = [0 for _ in range(N)]
C = [0 for _ in range(N)]
T = [0 for _ in range(N)]
for i in range(N):
	if S[i] == 'A':
		A[i] = 1
	elif S[i] == 'G':
		G[i] = 1
	elif S[i] == 'C':
		C[i] = 1
	elif S[i] == 'T':
		T[i] = 1
ans = 0
for i in range(N):
	Asum = 0
	Gsum = 0
	Tsum = 0
	Csum = 0
	for j in range(i, N):
		Asum += A[j]
		Gsum += G[j]
		Csum += C[j]
		Tsum += T[j]
		if Asum == Tsum and Csum == Gsum:
			ans += 1
print(ans)


from collections import defaultdict
(N, S) = input().split()
N = int(N)
cnt = defaultdict(int)
answer = 0
for i in range(N):
	for s in 'AGCT':
		cnt[s] = 0
	for j in range(i + 1, N, 2):
		cnt[S[j - 1]] += 1
		cnt[S[j]] += 1
		if cnt['A'] == cnt['T'] and cnt['C'] == cnt['G']:
			answer += 1
print(answer)


(N, S) = input().split()
N = int(N)
left_AT_number = [0] * (N + 1)
left_CG_number = [0] * (N + 1)
AT = 0
CG = 0
for j in range(N):
	if S[j] == 'A':
		AT += 1
	elif S[j] == 'T':
		AT -= 1
	elif S[j] == 'C':
		CG += 1
	else:
		CG -= 1
	left_AT_number[j + 1] = AT
	left_CG_number[j + 1] = CG
ans = 0
i_CG = 0
i_AT = 0
for i in range(N):
	i_CG = left_CG_number[i]
	i_AT = left_AT_number[i]
	for k in range(i + 1, N + 1):
		if i_CG - left_CG_number[k] == 0 and i_AT - left_AT_number[k] == 0:
			ans += 1
print(ans)


(n, s) = input().split()
n = int(n)
ans = 0
(AT, GC) = (0, 0)
cnt = {}
cnt[0, 0] = 1
for i in s:
	if i == 'A':
		AT += 1
	elif i == 'T':
		AT -= 1
	elif i == 'G':
		GC += 1
	elif i == 'C':
		GC -= 1
	if (AT, GC) in cnt:
		ans += cnt[AT, GC]
		cnt[AT, GC] += 1
	else:
		cnt[AT, GC] = 1
print(ans)


from collections import *
(n, s) = input().split()
x = y = r = 0
d = Counter()
for c in s:
	d[x, y] += 1
	if c == 'A':
		x += 1
	elif c == 'T':
		x -= 1
	elif c == 'C':
		y += 1
	elif c == 'G':
		y -= 1
	r += d[x, y]
print(r)


line = input().split()
(n, s) = (int(line[0]), list(line[1]))
ans = 0
for i in range(n - 1):
	d = {'A': 0, 'T': 0, 'C': 0, 'G': 0}
	d[s[i]] += 1
	for j in range(i + 1, n):
		d[s[j]] += 1
		if d['A'] == d['T'] and d['C'] == d['G']:
			ans += 1
print(ans)


from collections import defaultdict
(N, s) = input().split()
n = int(N)
ans = 0
for i in range(n):
	dic = defaultdict(int)
	for j in range(i, n):
		dic[s[j]] += 1
		if dic['A'] == dic['T'] and dic['G'] == dic['C']:
			ans += 1
print(ans)


def main():
	(n, s) = input().split()
	n = int(n)
	ans = 0
	for i in range(n):
		at = gc = 0
		for si in s[i:]:
			if si == 'A':
				at += 1
			elif si == 'T':
				at -= 1
			elif si == 'C':
				gc -= 1
			else:
				gc += 1
			if at == 0 and gc == 0:
				ans += 1
	print(ans)
main()


from itertools import combinations, permutations, combinations_with_replacement, product, accumulate
(n, s) = input().split()
n = int(n)
a = [0] * n
t = [0] * n
g = [0] * n
c = [0] * n
for i in range(n):
	if s[i] == 'A':
		a[i] += 1
	elif s[i] == 'T':
		t[i] += 1
	elif s[i] == 'G':
		g[i] += 1
	else:
		c[i] += 1
a = [0] + list(accumulate(a))
t = [0] + list(accumulate(t))
g = [0] + list(accumulate(g))
c = [0] + list(accumulate(c))
ans = 0
for i in range(1, n + 1):
	for j in range(i + 1, n + 1, 2):
		if a[j] - a[i - 1] == t[j] - t[i - 1] and g[j] - g[i - 1] == c[j] - c[i - 1]:
			ans += 1
print(ans)


from collections import defaultdict as dd
(n, s) = (i for i in input().split())
(n, ans) = (int(n), 0)
(x, d) = ([[0] * 2 for i in range(n + 1)], dd(int))
for i in range(n):
	for j in range(2):
		x[i + 1][j] = x[i][j]
	if s[i] == 'A':
		x[i + 1][0] = x[i][0] + 1
	elif s[i] == 'T':
		x[i + 1][0] = x[i][0] - 1
	elif s[i] == 'C':
		x[i + 1][1] = x[i][1] + 1
	else:
		x[i + 1][1] = x[i][1] - 1
for (i, j) in x:
	z = str(i) + ' ' + str(j)
	d[z] += 1
for i in d.values():
	ans += i * (i - 1) // 2
print(ans)


(N, S) = list(map(str, input().split()))
N = int(N)
ans = 0
for i in range(N):
	A = {'A': 0, 'T': 0, 'G': 0, 'C': 0}
	for j in range(i, N):
		A[S[j]] += 1
		if A['A'] == A['T'] and A['G'] == A['C']:
			ans += 1
print(ans)


(N, S) = input().split()
N = int(N)
AT = [0] * (N + 1)
CG = [0] * (N + 1)
for n in range(N):
	if S[n] == 'A':
		AT[n + 1] = 1
	if S[n] == 'T':
		AT[n + 1] = -1
	if S[n] == 'C':
		CG[n + 1] = 1
	if S[n] == 'G':
		CG[n + 1] = -1
for n in range(1, N + 1):
	AT[n] += AT[n - 1]
	CG[n] += CG[n - 1]
ans = 0
for i in range(N):
	for j in range(i + 2, N + 1, 2):
		at = AT[j] - AT[i]
		cg = CG[j] - CG[i]
		if at == 0 and cg == 0:
			ans += 1
print(ans)


(N, s) = input().split()
n = int(N)
ans = 0
for i in range(n):
	dic = {'A': 0, 'T': 0, 'G': 0, 'C': 0}
	for j in range(i, n):
		dic[s[j]] += 1
		if dic['A'] == dic['T'] and dic['G'] == dic['C']:
			ans += 1
print(ans)


(N, S) = input().split()
N = int(N)
ans = 0
t = {}
t[0, 0] = 1
(a, b) = (0, 0)
for c in S:
	if c == 'A':
		a += 1
	elif c == 'T':
		a -= 1
	elif c == 'C':
		b += 1
	else:
		b -= 1
	if (a, b) in t:
		ans += t[a, b]
		t[a, b] += 1
	else:
		t[a, b] = 1
print(ans)


import sys
import io
import math
import collections
import decimal
import itertools
from queue import PriorityQueue
import bisect

def input():
	return sys.stdin.readline()[:-1]
sys.setrecursionlimit(1000000)

def solve(N, S):
	n = 0
	for i in range(-1, N - 1):
		count_a = 0
		count_g = 0
		count_c = 0
		count_t = 0
		for j in range(i + 1, N):
			if S[j] == 'A':
				count_a += 1
			elif S[j] == 'G':
				count_g += 1
			elif S[j] == 'C':
				count_c += 1
			elif S[j] == 'T':
				count_t += 1
			if count_a == count_t and count_c == count_g:
				n += 1
	return n

def main():
	(N, S) = input().split()
	N = int(N)
	a = solve(N, S)
	print(a)

def __starting_point():
	main()
__starting_point()


(n, s) = input().split()
n = int(n)
ans = 0
for i in range(n):
	(AT, GC) = (0, 0)
	for j in range(i, n):
		if s[j] == 'A':
			AT += 1
		if s[j] == 'T':
			AT -= 1
		if s[j] == 'G':
			GC += 1
		if s[j] == 'C':
			GC -= 1
		if AT == 0 and GC == 0:
			ans += 1
print(ans)


from collections import Counter
(n, s) = input().split()
n = int(n)
d = {'A': (0, +1), 'T': (0, -1), 'G': (+1, 0), 'C': (-1, 0)}
cs = [(0, 0)] * (n + 1)
for i in range(n):
	(a1, b1) = cs[i]
	(a2, b2) = d[s[i]]
	cs[i + 1] = (a1 + a2, b1 + b2)
cnt = Counter(cs)
ans = sum((m * (m - 1) // 2 for m in list(cnt.values())))
print(ans)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

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

def inpl():
	return list(map(int, input().split()))

def inpls():
	return list(map(str, input().split()))
from math import gcd, floor, ceil, factorial
import itertools as it
from collections import deque, defaultdict
from collections import Counter

def lcd(a, b):
	return a * b // gcd(a, b)

def chmin(dp, i, x):
	if x < dp[i]:
		dp[i] = x
		return True
	return False

def chmax(dp, i, x):
	if x > dp[i]:
		dp[i] = x
		return True
	return False
(N, S) = input().split()
N = int(N)
S = S.rstrip()
A = [0] * (N + 1)
T = [0] * (N + 1)
C = [0] * (N + 1)
G = [0] * (N + 1)
for i in range(N):
	s = S[i]
	A[i + 1] = A[i] + (1 if s == 'A' else 0)
	T[i + 1] = T[i] + (1 if s == 'T' else 0)
	C[i + 1] = C[i] + (1 if s == 'C' else 0)
	G[i + 1] = G[i] + (1 if s == 'G' else 0)
ans = 0
for i in range(N):
	j = i + 2
	while j <= N:
		if A[j] - A[i] == T[j] - T[i] and C[j] - C[i] == G[j] - G[i]:
			ans += 1
		j += 2
print(ans)


def hoge():
	(N, S) = input().split()
	N = int(N)
	ans = 0
	for i in range(N):
		(at, cg) = (0, 0)
		for j in range(i, N):
			X = S[j]
			if X == 'A':
				at += 1
			elif X == 'T':
				at -= 1
			elif X == 'C':
				cg += 1
			else:
				cg -= 1
			if at == 0 and cg == 0:
				ans += 1
	print(ans)
hoge()


(n, s) = input().split()
n = int(n)
ans = 0
for i in range(n):
	(c1, c2) = (0, 0)
	for j in range(i, n):
		if s[j] == 'A':
			c1 += 1
		elif s[j] == 'T':
			c1 -= 1
		elif s[j] == 'C':
			c2 += 1
		elif s[j] == 'G':
			c2 -= 1
		if c1 == c2 == 0:
			ans += 1
print(ans)


from collections import Counter
(n, s) = input().split()
n = int(n)
d = Counter()
(at, cg) = (0, 0)
d[at, cg] = 1
ans = 0
for x in s:
	if x == 'A':
		at += 1
	elif x == 'T':
		at -= 1
	elif x == 'C':
		cg += 1
	else:
		cg -= 1
	ans += d[at, cg]
	d[at, cg] += 1
print(ans)


import collections
(n, s) = map(str, input().split())
ans = 0
for i in range(int(n)):
	cnt = {'A': 0, 'T': 0, 'G': 0, 'C': 0}
	cnt[s[i]] += 1
	for j in range(i + 1, int(n)):
		cnt[s[j]] += 1
		if cnt['A'] == cnt['T'] and cnt['C'] == cnt['G']:
			ans += 1
print(ans)


(n, s) = input().split()
n = int(n)
ans = 0
for start_ind in range(n):
	a_vs_t = 0
	g_vs_c = 0
	for endInd in range(start_ind, n):
		if s[endInd] == 'A':
			a_vs_t += 1
		elif s[endInd] == 'T':
			a_vs_t -= 1
		elif s[endInd] == 'G':
			g_vs_c += 1
		else:
			g_vs_c -= 1
		if a_vs_t == 0 and g_vs_c == 0:
			ans += 1
print(ans)


(N, S) = input().split()
N = int(N)
result = 0
for i in range(N):
	(a, b) = (0, 0)
	for c in S[i:]:
		if c == 'A':
			a += 1
		elif c == 'T':
			a -= 1
		elif c == 'C':
			b += 1
		else:
			b -= 1
		if a == 0 and b == 0:
			result += 1
print(result)


(N, S) = input().split()
N = int(N)
count = 0
for i in range(N):
	num_A = num_T = num_C = num_G = 0
	for char in S[i:N]:
		if char == 'A':
			num_A += 1
		elif char == 'T':
			num_T += 1
		elif char == 'C':
			num_C += 1
		else:
			num_G += 1
		if num_A == num_T and num_C == num_G:
			count += 1
print(count)


import collections
g = input().split()
N = int(g[0])
l = g[1]
S = [[0, 0, 0, 0] for i in range(N + 1)]
dic = {'A': 0, 'T': 1, 'C': 2, 'G': 3}
X = [[0, 0] for i in range(N + 1)]
X[0] = tuple(X[0])
for i in range(1, N + 1):
	S[i] = S[i - 1].copy()
	S[i][dic[l[i - 1]]] += 1
	X[i][0] = S[i][0] - S[i][1]
	X[i][1] = S[i][2] - S[i][3]
	X[i] = tuple(X[i])
D = collections.Counter(X)
ans = 0
for v in D.values():
	ans += v * (v - 1) // 2
print(ans)


(N, S) = list(map(str, input().split()))
N = int(N)
ans = 0
for i in range(N):
	c1 = 0
	c2 = 0
	for j in range(i, N):
		if S[j] == 'A':
			c1 += 1
		elif S[j] == 'T':
			c1 -= 1
		elif S[j] == 'G':
			c2 += 1
		else:
			c2 -= 1
		if c1 == 0 and c2 == 0:
			ans += 1
print(ans)


(n, sl) = map(str, input().split())
sl = list(sl)
n = int(n)
atl = [0]
cgl = [0]
at = 0
cg = 0
for s in sl:
	if s == 'A':
		at += 1
	elif s == 'T':
		at -= 1
	elif s == 'C':
		cg += 1
	else:
		cg -= 1
	atl.append(at)
	cgl.append(cg)
ans = 0
for i in range(n + 1):
	for j in range(i + 1, n + 1):
		if atl[j] == atl[i] and cgl[j] == cgl[i]:
			ans += 1
print(ans)


(_, S) = input().split()
N = len(S)
ans = 0
for i in range(0, N - 1):
	AT = 0
	CG = 0
	if S[i] == 'A':
		AT += 1
	elif S[i] == 'T':
		AT -= 1
	elif S[i] == 'C':
		CG += 1
	elif S[i] == 'G':
		CG -= 1
	for j in range(i + 1, N):
		if S[j] == 'A':
			AT += 1
		elif S[j] == 'T':
			AT -= 1
		elif S[j] == 'C':
			CG += 1
		elif S[j] == 'G':
			CG -= 1
		if AT == 0 and CG == 0:
			ans += 1
print(ans)


(n, s) = input().split()
n = int(n)
ans = 0
for i in range(n):
	(a, t, g, c) = (0, 0, 0, 0)
	for j in range(i, n):
		if s[j] == 'A':
			a += 1
		elif s[j] == 'T':
			t += 1
		elif s[j] == 'G':
			g += 1
		else:
			c += 1
		if a == t and g == c:
			ans += 1
print(ans)


(n, s) = input().split()
n = int(n)
at = [0] * (n + 1)
cg = [0] * (n + 1)
for i in range(n):
	AT = 0
	CG = 0
	if s[i] == 'A':
		AT = 1
	elif s[i] == 'T':
		AT = -1
	elif s[i] == 'C':
		CG = 1
	else:
		CG = -1
	at[i + 1] = at[i] + AT
	cg[i + 1] = cg[i] + CG
ans = 0
for i in range(n):
	for j in range(i + 1, n + 1):
		AT = at[j] - at[i]
		CG = cg[j] - cg[i]
		if AT == 0 and CG == 0:
			ans += 1
print(ans)


def main():
	l = list(input().split())
	word = list(l[1])
	count = 0
	for i in range(int(l[0])):
		at_num = 0
		cg_num = 0
		for j in word[i:int(l[0])]:
			if j == 'A':
				at_num += 1
			elif j == 'T':
				at_num -= 1
			elif j == 'G':
				cg_num += 1
			elif j == 'C':
				cg_num -= 1
			if at_num == 0 and cg_num == 0:
				count += 1
	print(count)

def __starting_point():
	main()
__starting_point()


(N, S) = input().split()
N = int(N) + 1
ans = 0
for i in range(N):
	counts = {base: 0 for base in 'ATGC'}
	for j in range(i + 2, N, 2):
		counts[S[j - 2]] += 1
		counts[S[j - 1]] += 1
		if counts['A'] == counts['T'] and counts['G'] == counts['C']:
			ans += 1
print(ans)


(N, S) = map(str, input().split())
N = int(N)
ans = 0
for i in range(N):
	a = 0
	t = 0
	c = 0
	g = 0
	for j in range(i, N):
		if S[j] == 'A':
			a += 1
		elif S[j] == 'T':
			t += 1
		elif S[j] == 'C':
			c += 1
		else:
			g += 1
		if a == t and c == g:
			ans += 1
print(ans)


(N, S) = input().split()
(N, a) = (int(N), 0)
for i in range(N):
	(c1, c2) = (0, 0)
	for s in S[i:]:
		if s == 'A':
			c1 += 1
		if s == 'T':
			c1 -= 1
		if s == 'C':
			c2 += 1
		if s == 'G':
			c2 -= 1
		if c1 == 0 and c2 == 0:
			a += 1
print(a)


from math import gcd
from itertools import combinations, permutations, accumulate, product, combinations_with_replacement
from collections import deque, defaultdict, Counter
import decimal
import re
import math
import bisect
import heapq
import sys
sys.setrecursionlimit(10000000)
mod = 10 ** 9 + 7
INF = float('inf')
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
from sys import stdin
readline = stdin.readline

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

def readTuples():
	return tuple(map(int, readline().split()))

def I():
	return int(readline())
(N, S) = input().split()
N = int(N)
ans = 0
for i in range(N):
	a = 0
	t = 0
	c = 0
	g = 0
	for j in range(i, N):
		if S[j] == 'A':
			a += 1
		elif S[j] == 'T':
			t += 1
		elif S[j] == 'C':
			c += 1
		else:
			g += 1
		if a == t and c == g:
			ans += 1
print(ans)


(n, S) = map(str, input().rstrip().split(' '))
n = int(n)
S = list(S)
cnt = 0
ac = 0
cg = 0

def nC2(num):
	ret = num * (num - 1) // 2
	return ret
Sum = []
for (i, s) in enumerate(S):
	if s == 'A':
		ac += 1
	elif s == 'T':
		ac -= 1
	elif s == 'C':
		cg += 1
	elif s == 'G':
		cg -= 1
	Sum.append((ac, cg))
cnt = 0
Table = {}
for t in Sum:
	if t == (0, 0):
		cnt += 1
	if t in Table:
		Table[t] += 1
	else:
		Table[t] = 1
for table in Table:
	tmp = Table[table]
	tmp = nC2(tmp)
	cnt += tmp
print(cnt)


from collections import Counter
(N, S) = input().split()
N = int(N)
(AT, CG) = (0, 0)
d = Counter()
d[AT, CG] = 1
ans = 0
for i in range(N):
	if S[i] == 'A':
		AT += 1
	elif S[i] == 'T':
		AT -= 1
	elif S[i] == 'C':
		CG += 1
	else:
		CG -= 1
	ans += d[AT, CG]
	d[AT, CG] += 1
print(ans)


(n, s) = input().split()
n = int(n)
s_l = list(s)
c = 0
for i in range(n - 1):
	d = {'A': 0, 'T': 0, 'C': 0, 'G': 0}
	for j in range(i + 2, n + 1, 2):
		d[s[j - 1]] += 1
		d[s[j - 2]] += 1
		if d['A'] == d['T'] and d['C'] == d['G']:
			c += 1
print(c)