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: interview

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

# 各区画Tが自分自身を並べ替えた文字列と相補的であるかどうかを調べていく。

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(cnt)
        
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:
            #print(i,k)
            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(cnt, ans)
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)

# 問題文の意味はまったくわからんが、とりあえず部分列でAとTの数およびCとGの数が同じところの数、ってこと？
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)


n,s = input().split()
n = int(n)

ans = 0

for i in range(n):
  d = {"A":0,"T":0,"G":0,"C":0,}
  for j in range(i,n):
    d[s[j]] += 1
    
    if d["A"] == d["T"] and d["G"] == d["C"]:
      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)

#region Header
#!/usr/bin/env python3
# from typing import *

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

# _INPUT = """10 AAATACCGCG
# """
# sys.stdin = io.StringIO(_INPUT)



# def solve(N: int, S: str) -> int:
def solve(N, S):
    # count_a = [0 for _ in range(N+1)]
    # count_g = [0 for _ in range(N+1)]
    # count_c = [0 for _ in range(N+1)]
    # count_t = [0 for _ in range(N+1)]
    # for i in range(1, N + 1):
    #     count_a[i] = count_a[i-1]
    #     count_g[i] = count_g[i-1]
    #     count_c[i] = count_c[i-1]
    #     count_t[i] = count_t[i-1]
    #     if S[i-1] == 'A':
    #         count_a[i] += 1
    #     elif S[i-1] == 'G':
    #         count_g[i] += 1
    #     elif S[i-1] == 'C':
    #         count_c[i] += 1
    #     elif S[i-1] == 'T':
    #         count_t[i] += 1

    # i文字目からj文字目までの（Aの数）=（Tの数）and（Cの数）=（Gの数）となる (i,j)
    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) 


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(cnt, ans)
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
# sys.setrecursionlimit(10**6)

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

# import decimal
# from decimal import Decimal
# decimal.getcontext().prec = 10

# from heapq import heappush, heappop, heapify
# import math
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)

# editorial

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):
        # print(start_ind, endInd)

        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])
    #print(str(S[i]) + " " + str(X[i]))
D = collections.Counter(X)
#print(D)
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
    # print(AT,CG)
    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(S[i:j+1],AT,CG,ans)
            
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でローカル変数を扱えば早くなるらしい
#インデントミスしまくりました

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

import sys
from collections import *
input = sys.stdin.readline

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)


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 = input().split()
ans = 0
for j in range(int(n)):
    c1, c2 = 0, 0
    for i in range(j, int(n)):
        if s[i] == 'T': c1 += 1
        elif s[i] == 'A': c1 -= 1
        elif s[i] == 'C': c2 += 1
        else: c2 -= 1
        if c1 == 0 and c2 == 0: 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 = list(map(str, input().split()))
n = int(n)
ans = 0
for i in range(n):
    at, cg = 0, 0
    for j in range(i, n):
        if s[j] == 'A':
            at += 1
        elif s[j] == 'T':
            at -= 1
        elif s[j] == 'C':
            cg += 1
        else:
            cg -= 1
        if at == 0 and cg == 0:
            ans += 1
print(ans)


n, s = map(str, input().split())
n = int(n)
ans = 0
for i in range(n):
    at = 0
    cg = 0
    for j in range(i,n):
        if s[j] == 'A':
            at += 1
        elif s[j] == 'T':
            at -= 1
        elif s[j] == 'C':
            cg += 1
        else:
            cg -= 1
        if at == 0 and cg == 0:
            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 statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from math import gcd
from itertools import combinations,permutations,accumulate, product, combinations_with_replacement # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect
import heapq
#
# set型だと、 | と & が使えるよ
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
#
# インデックス系
# int min_y = max(0, i - 2), max_y = min(h - 1, i + 2);
# int min_x = max(0, j - 2), max_x = min(w - 1, j + 2);
#
#
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
# mod = 9982443453
# mod = 998244353
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)

N, S = input().split()
N = int(N)

cnt_AT = [0] * (N+1)
cnt_CG = [0] * (N+1)

for n in range(N):
    if S[n] == "A":
        cnt_AT[n+1] = cnt_AT[n] + 1
        cnt_CG[n+1] = cnt_CG[n]
    if S[n] == "T":
        cnt_AT[n+1] = cnt_AT[n] - 1
        cnt_CG[n+1] = cnt_CG[n]
    if S[n] == "C":
        cnt_AT[n+1] = cnt_AT[n]
        cnt_CG[n+1] = cnt_CG[n] + 1
    if S[n] == "G":
        cnt_AT[n+1] = cnt_AT[n]
        cnt_CG[n+1] = cnt_CG[n] - 1

ans = 0

for i in range(N-1):
    for j in range(i+2, N+1, 2):
        at = cnt_AT[j] - cnt_AT[i]
        cg = cnt_CG[j] - cnt_CG[i]
        if at == 0 and cg == 0:
            ans += 1

print(ans)


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)