Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

N = int(input())
A = input().split()

pear = 0

for i in range(N-1):
  for j in range(i+1, N):
    if (j - i) == (int(A[i]) + int(A[j])):
      pear += 1
      
print(pear)
  

### FIXED CODE ###

N = int(input())
A = input().split()

pear = 0

i_result = {}
j_result = {}

for i in range(N):
  result = str(i + int(A[i]))
  if result in i_result:
    i_result[result] += 1
  else:
    i_result[result] = 1

for j in range(N):
  result = str(j - int(A[j]))
  if result in j_result:
    j_result[result] += 1
  else:
    j_result[result] = 1

for k in i_result.keys():
  if k in j_result:
    pear += (i_result[k] * j_result[k])
      
      
print(pear)
### BUGGY CODE ###

# coding:utf-8

import sys
from collections import defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


n, k, l = LI()


def DFS(s, G, memo):
    q = [s]
    visited = set()
    while q:
        v = q.pop()
        visited.add(v)
        for nv in G[v]:
            if nv in visited:
                continue
            q.append(nv)

    for v in list(visited):
        memo[v] |= visited

    return memo


A = defaultdict(list)
B = defaultdict(list)
for _ in range(k):
    p, q = LI_()
    A[p].append(q)
    A[q].append(p)

for _ in range(l):
    r, s = LI_()
    B[r].append(s)
    B[s].append(r)


memo_a = defaultdict(set)
memo_b = defaultdict(set)

for i in range(n):
    if memo_a[i]:
        continue
    memo_a = DFS(i, A, memo_a)

for i in range(n):
    if memo_b[i]:
        continue
    memo_b = DFS(i, B, memo_b)

ans = []
for i in range(n):
    ans.append(len(memo_a[i] & memo_b[i]))

print(*ans)


### FIXED CODE ###

# coding:utf-8

import sys
from collections import defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


n, k, l = LI()

# UnionFind
class UnionFind:
    # 負: ルートで値は木の深さを表す
    # 正: 子で値は次のノードを表す
    def __init__(self, size: int) -> None:
        self.nodes = [-1] * size  # 初期状態では全てのノードがルート

    def find(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            self.nodes[x] = self.find(self.nodes[x])
            return self.nodes[x]

    def unite(self, x: int, y: int) -> None:
        root_x, root_y = self.find(x), self.find(y)
        if root_x != root_y:
            if self.nodes[root_x] != self.nodes[root_y]:  # グラフの高さが異なる場合
                # 木のランクが高い方のルートに併合させる
                # 併合後にランクの変動はない
                if self.nodes[root_x] < self.nodes[root_y]:
                    self.nodes[root_y] = root_x
                else:
                    self.nodes[root_x] = root_y
            else:
                # ランクが等しい木同士を併合させるので
                # 併合後は木のランクが1つ上がる
                self.nodes[root_x] += -1
                self.nodes[root_y] = root_x


ufa = UnionFind(n)
ufb = UnionFind(n)

for _ in range(k):
    a, b = LI_()
    ufa.unite(a, b)
for _ in range(l):
    a, b = LI_()
    ufb.unite(a, b)

cnt = defaultdict(int)
keys = []
for i in range(n):
    key = (ufa.find(i), ufb.find(i))
    cnt[key] += 1
    keys.append(key)

print(*[cnt[key] for key in keys])
### BUGGY CODE ###

from scipy.sparse.csgraph import floyd_warshall
n=int(input())
s=[[0]*n for _ in range(n)]
for i in range(n-1):
    a,b,c=map(int,input().split())
    s[a-1][b-1]=c
    s[b-1][a-1]=c
s=floyd_warshall(s)

q,k=map(int,input().split())
for i in range(q):
    ans=0
    x,y=map(int,input().split())
    ans+=s[x-1][k-1]
    ans+=s[k-1][y-1]
    print(int(ans))


### FIXED CODE ###

N=int(input())
edges=[list(map(int,input().split())) for i in range(N-1)]
Q,K=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(Q)]
root=[[] for _ in range(N)]
for a,b,c in edges:
        root[a-1].append((b-1,c))
        root[b-1].append((a-1,c))
d=[-1]*N
s=[K-1]
d[K-1]=0
while s:
        l=s.pop()

        for i,c in root[l]:
                if d[i]==-1:
                        d[i]=d[l]+c
                        s.append(i)
for i in range(Q):
        print(d[xy[i][0]-1]+d[xy[i][1]-1])
### BUGGY CODE ###

from collections import deque
N,M,L = map(int,input().split())
load = [[]for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    if c > L:
        continue
    load[a-1].append([b-1,c])
    load[b-1].append([a-1,c])
cost =[[float('inf')]*N for i in range(N)]
for i in range(N):
    queue = deque([i])
    cost[i][i] = 0
    while(queue):
        q = queue.popleft()
        gas = cost[i][q]
        for t,c in load[q]:
            if gas//L < (gas+c-1)//L :
                if (gas//L+1)*L+c < cost[i][t]:
                    cost[i][t] = (gas//L+1)*L+c
                    queue.append(t)
            else:
                if gas+c < cost[i][t]:
                    cost[i][t] = gas+c
                    queue.append(t)
Q = int(input())
for i in range(Q):
    s,t = map(int,input().split())
    ans = cost[s-1][t-1]
    if ans == float('inf'):
        print(-1)
    else:
        print((ans-1)//L)
     


### FIXED CODE ###

import sys
imput = sys.stdin.readline
def func(d):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])
    return d
N,M,L = map(int,input().split())
road = [[10**10]*N for i in range(N)]
for i in range(N):
    road[i][i] = 0
for i in range(M):
    a,b,c = map(int,input().split())
    road[a-1][b-1] = c
    road[b-1][a-1] = c
road = func(road)
ans = [[10**5]*N for i in range(N)]
for i in range(N):
    for j in range(N):
        if road[i][j] <= L:
            ans[i][j] = 1
ans = func(ans)
for i in range(int(input())):
    a,b = map(int,input().split())
    o = ans[a-1][b-1]
    if o == 10**5:
        print(-1)
    else:
        print(o-1)
### BUGGY CODE ###

# coding: utf-8
# Your code here!

# coding: utf-8
# Your code here!
# coding: utf-8
import sys
sys.setrecursionlimit(10000000)

#const
dxdy=((1,0),(0,1))
# my functions here!
def pin(type=int):
    return map(type,input().rstrip().split())

def resolve():  
    N=int(input())
    S=input()
    r,g,b=[],[],[]
    for i,s in enumerate(S):
        if s=="R":r.append(i)
        elif s=="B":b.append(i)
        else: g.append(i)
    #print("columnis",r,g,b)
    #RGBのリストが作れたので、このうち１個ずつとっていけば
    #<1>の条件を満たすことができる（ijkの順序が決まっていることから、
    #最後にこれらが<2>を満たすことを確認する？または、満たさないものを除く
    #<2> i<=j<=k　に対して　j-i = k-j でない
    #"この式を整理すると"k-j*2+i=0ではない:i+j+k=j*3ではない
    #逆にこの式を満たす（平均の関係になっているなら、jは必ず真ん中になる
    
    cnt=0
    for R in r:
        for G in g:
            s=2*R-G
            t=2*G-R
            flag1= (0<=s<=N+1)
            flag2= (0<=t<=N+1)
            flag3= ((R+G)%2==0)
            
            tx=0
            for B in b:
                conds=flag1+flag2+flag3
                #print(conds,(flag1,flag2,flag3))
                #print(B,t)
                if flag1 == 1:
                    if B==s:
                        flag1=0
                        tx+=1
                if flag2 == 1:
                    if B==t:
                        flag2=0
                        tx+=1
                if flag3 == 1:
                    if B==((R+G)//2):
                        flag3=0
                        tx+=1
                if conds==0 or B==b[-1]:
                    #print(t)
                    cnt+=tx
                    break
                    #print(R,G,B)
    print(len(r)*len(g)*len(b)-cnt)
        
"""         
#printデバッグ消した？
#前の問題の結果見てないのに次の問題に行くの？
"""
"""
お前カッコ閉じ,るの忘れてるだろ
"""
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """4
RRGB"""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """39
RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB"""
        output = """1800"""
        self.assertIO(input, output)


if __name__ == "__main__":
    #unittest.main()
    resolve()


### FIXED CODE ###

#%%code
def resolve():
    N=int(input())
    S=input()
    RGB=[0,0,0]
    subcnt=0
    for i,c in enumerate(S):
        if c=="R":RGB[0]+=1
        if c=="G":RGB[1]+=1
        if c=="B":RGB[2]+=1
            
        for j in range(i+1,N):
            s=S[j]
            k=j*2-i
            if k<N :
                x=S[k]
                if   x!=s and s!=c and x!=c :
                    #print(i,j,k)
                    
                    subcnt+=1
            else:break

    #print(RGB,subcnt)
    A=RGB[0]*RGB[1]*RGB[2]
    print(A-subcnt)
            
#%%submit!
resolve()
### BUGGY CODE ###

from heapq import heappop, heappush, heapify
from collections import deque
import bisect
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = [int(i) for i in input().split()]
A.sort()
for i in range(M):
  B,C = map(int, input().split())
  for j in range(B):
    idx = bisect.insort_left(A,C)
print(sum(A[-N:]))

### FIXED CODE ###

N, M = map(int, input().split())
A = [int(i) for i in input().split()]
table = []
for i in range(N):
  table.append((A[i],1))
for i in range(M):
  b,c = map(int, input().split())
  table.append((c,b))
table.sort()
count = 0
ans = 0
while True:
  c, b = table.pop()
  if b <= N - count:
    ans += c*b
    count += b
  else:
    ans += (N-count)*c
    break
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
# import sys


def solve(N: int):
    for i in range(1, 3501):
        for j in range(1, 3501):
            z = 4*i*j - N*j - N*i
            if z != 0:
                h, r = divmod((N*i*j), z)
                if r == 0 and 0 <= h:
                    print(h, i, j)
                    exit()
            

    return

N = int(input())
solve(N)


# # Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
# def main():
#     def iterate_tokens():
#         for line in sys.stdin:
#             for word in line.split():
#                 yield word
#     tokens = iterate_tokens()
#     N = int(next(tokens))  # type: int
#     solve(N)

# if __name__ == '__main__':
#     main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int):
    for i in range(1, 3501):
        for j in range(i, 3501):
            z = 4*i*j - N*(j+i)
            if z > 0:
                h, r = divmod((N*i*j), z)
                if r == 0:
                    print(h, i, j)
                    exit()
            

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()


# #!/usr/bin/env python3
# n = int(input())
# for i in range(1, 3501):
#   for j in range(1, 3501):
#     seed = 4 * i * j - n * (i + j) 
#     if seed > 0:
#       k, mod = divmod(n * i * j, seed) 
#       if mod == 0:
#         print(i, j, k)
#         exit()
### BUGGY CODE ###

from collections import deque
N, M, K = map(int, input().split())
A = [[] for i in range(N)]
B = [[] for i in range(N)]
for i in range(M):
  a, b = map(lambda x:int(x)-1, input().split())
  A[a].append(b)
  A[b].append(a)
for i in range(K):
  a, b = map(lambda x:int(x)-1, input().split())
  B[a].append(b)
  B[b].append(a)
P = [-1 for i in range(N)]
k = 0
for i in range(N):
  if P[i] == -1:
    k += 1
    P[i] = k
    d = deque([i])
    while len(d):
      s = d.pop()
      for t in A[s]:
        if P[t] == -1:
          P[t] = k
          d.append(t)
for i in range(N):
  ans = 0
  for j in range(N):
    if P[i] == P[j] and i != j and j not in A[i] and j not in B[i]:
      ans += 1
  print(ans)

### FIXED CODE ###

from collections import deque
N, M, K = map(int, input().split())
A = [[] for i in range(N)]
B = [[] for i in range(N)]
for i in range(M):
  a, b = map(lambda x:int(x)-1, input().split())
  A[a].append(b)
  A[b].append(a)
for i in range(K):
  a, b = map(lambda x:int(x)-1, input().split())
  B[a].append(b)
  B[b].append(a)
P = [-1 for i in range(N)]
Q = []
k = -1
for i in range(N):
  if P[i] == -1:
    q = 1
    k += 1
    P[i] = k
    d = deque([i])
    while len(d):
      s = d.pop()
      for t in A[s]:
        if P[t] == -1:
          P[t] = k
          q += 1
          d.append(t)
    Q.append(q)
for i in range(N):
  ans = Q[P[i]] - len(A[i]) - 1
  for j in B[i]:
    if P[i] == P[j]:
      ans -= 1
  print(ans)
### BUGGY CODE ###

N = int(input())
C = list(input())

C_l = []
ans = []
for _ in range(N):
    w = C_l.count("W")
    r = C.count("R")
    ans.append(max(w, r))
    C_l.append(C.pop(0))
w = C_l.count("W")
r = C.count("R")
ans.append(max(w, r))
print(min(ans))

### FIXED CODE ###

N = int(input())
C = list(input())

r = C.count("R")

cnt = 0
for i in range(r):
    if C[i] == "W":
        cnt += 1
        
print(cnt)
### BUGGY CODE ###

N = int(input())
#S = [input() for i in range(N)]
S=[]
ans = 0

for i in range(N):
    S.append(''.join(sorted(list(input()))))

for i in range(N):
    for j in range(i+1,N):
        if S[i]==S[j]:
            ans+=1
print(ans)

### FIXED CODE ###

N = int(input())
#S = [input() for i in range(N)]
S=[]
ans_dic={}
temp_ans = 1
ans = 0

for i in range(N):
    temp = sorted(list(input()))
    temp = ''.join(temp)
    #S.append(''.join(temp))
    #alpha_dic[temp[0]].append(i) 
    if temp in ans_dic:
        ans_dic[temp] += 1
    else:
        ans_dic[temp] = 1
    
for key,value in ans_dic.items():
    ans += value*(value-1)/2

print(round(ans))
### BUGGY CODE ###

# E - Active Infants

n = int(input())
a = list(map(int, input().split()))
assert len(a) == n

# 添字のリスト
p = list(range(n))
p.sort(key=lambda i: a[i])

# dp[(j, i)] = 位置jから幅iの区間に小さい方からi個を配置したときの最大うれしさ
dp = {(j, 0): 0 for j in range(n + 1)}

for i in range(n):
    for j in range(n - i):
        dp[(j, i + 1)] = \
            max(dp[(j,     i)] + a[p[i]] * abs(p[i] - (j + i)),
                dp[(j + 1, i)] + a[p[i]] * abs(p[i] - j))

print(dp[(0, n)])


### FIXED CODE ###

# E - Active Infants

n = int(input())
a = list(map(int, input().split()))
assert len(a) == n

# 添字のリスト
p = list(range(n))
p.sort(key=lambda i: a[i])

# dp[(j, i)] = 位置jから幅iの区間に小さい方からi個を配置したときの最大うれしさ
dp = {(j, 0): 0 for j in range(n + 1)}

for i in range(n):
    for j in range(n - i):
        dp[(j, i + 1)] = \
            max(dp[(j,     i)] + a[p[i]] * abs(p[i] - (j + i)),
                dp[(j + 1, i)] + a[p[i]] * abs(p[i] - j))

print(dp[(0, n)])
### BUGGY CODE ###

import fractions

K = int(input())
g = []
for i in range(1, K+1):
    for j in range(1, i+1):
        for k in range(1, j+1):
            a = fractions.gcd(i, j)
            b = fractions.gcd(a, k)
            if i != j != k:
                g.append(b)
                g.append(b)
                g.append(b)
                g.append(b)
                g.append(b)
                g.append(b)
            elif i == j == k:
                g.append(b)
            else:
                g.append(b)
                g.append(b)
                g.append(b)

print(sum(g))

### FIXED CODE ###

import math

K = int(input())
g = 0
for i in range(1, K+1):
    for j in range(1, i+1):
        for k in range(1, j+1):
            a = math.gcd(i, j)
            b = math.gcd(a, k)
            if i != j != k:
                g += b*6
            elif i == j == k:
                g += b
            else:
                g += b*3

print(g)
### BUGGY CODE ###

def main():
    n, m = map(int, input().split())
    p = [0] * m
    S = [0] * m
    for i in range(m):
        p[i], S[i] = map(str , input().split())
        p = [int(s) for s in p]
    # 問題によってカウントしたい
    WA = [0] * (n+1)
    # 全体として何個かがわかればいい
    AC = [False] * (n+1)
    for i in range(m):
        # AC出ててなくて、WAでたらカウント、AC出たらフラグ変更        
        if not AC[p[i]]:
            if S[i] == 'WA':
                WA[p[i]] += 1
            else:
                AC[p[i]] = True
        # AC出てるから次へ
        else:
            continue
    wa = sum(WA)
    ac = sum(AC)
    print(ac, wa)
        
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n, m = map(int, input().split())
    P = [0] * m
    S = [0] * m
    for i in range(m):
        P[i], S[i] = map(str , input().split())
    # p = [int(s) for s in p]
    # 問題によってカウントしたい
    WA = [0] * (n+1)
    # 全体として何個かがわかればいい
    AC = [False] * (n+1)
    cnt = 0
    for i in range(m):
        p = int(P[i])
        if AC[p]:
            continue
        else:
            if S[i] == 'WA':
                WA[p] += 1
            else:
                AC[p] = True
                cnt += WA[p]
    # wa = sum(WA)
    ac = sum(AC)
    print(ac, cnt)
        
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
print(0, flush=True)

for i in [0, n - 1]:
    res = input()
    if res == "Vacant":
        exit()


left = 0
right = n
gen = res


while True:
    mid = (left + right) // 2
    print(mid, flush=True)
    res = input()

    if res == "Vacant":
        exit()

    if gen == res:
        if (mid - left) % 2:
            right = mid
        else:
            left = mid
    else:
        if (mid - left) % 2:
            left = mid
            gen = res
        else:
            right = mid

### FIXED CODE ###

n = int(input())

print(0, flush=True)
res = input()
if res == "Vacant":
    exit()

left = 0
right = n
gen = res


while True:
    mid = (left + right) // 2
    print(mid, flush=True)
    res = input()

    if res == "Vacant":
        exit()

    if gen == res:
        if (mid - left) % 2:
            right = mid
        else:
            left = mid
    else:
        if (mid - left) % 2:
            left = mid
            gen = res
        else:
            right = mid
### BUGGY CODE ###

from collections import deque

S = input()
Q = int(input())

S = deque(S)

for _ in range(Q):
    query = list(input().split())
    if query[0] == '1':
        S.reverse()
    elif query[0] == '2':
        if query[1] == '1':
            S.appendleft(query[2])
        elif query[1] == '2':
            S.append(query[2])
            
result = ''.join(S)
print(result)

### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())

S = deque(S)
reverse = False

for _ in range(Q):
    query = input()
    if query[0] == '1':
        reverse = not reverse
    elif query[0] == '2':
        _, F, C = query.split()
        if F == '1':
            if reverse:
                S.append(C)
            else:
                S.appendleft(C)
        elif F == '2':
            if reverse:
                S.appendleft(C)
            else:
                S.append(C)
            
result = ''.join(S)
if reverse:
    result = result[::-1]
print(result)
### BUGGY CODE ###

n, m = map(int, input().split())
a = []
b = []
for i in range(n):
    x, y = map(int, input().split())
    a.append(x)
    b.append(y)

count = 0
money = 0
while count < m:
    count += b[a.index(min(a))]
    if count <= m:
        money += a[a.index(min(a))] * b[a.index(min(a))]
    else:
        money += a[a.index(min(a))] * (m - count + b[a.index(min(a))])

    del b[a.index(min(a))]
    del a[a.index(min(a))]
    
print(money)

### FIXED CODE ###

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(n)]

ab.sort(key=lambda x: x[0])

count = 0
money = 0
while True:
    count += ab[0][1]
    if count < m:
        money += ab[0][0] * ab[0][1]
        del ab[0]
    else:
        money += ab[0][0] * (m - count + ab[0][1])
        break

print(money)
### BUGGY CODE ###

n = int(input())
*A, = map(int, input().split())
a, b, c = A.count(1), A.count(2), A.count(3)
DP = [[[0.0 for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]
for k in range(c+1):
    for j in range(n-k+1):
        for i in range(n-k-j+1):
            if i+j+k == 0:
                continue
            DP[i][j][k] = n
            if i > 0:
                DP[i][j][k] += DP[i-1][j][k]*i
            if j > 0:
                DP[i][j][k] += DP[i+1][j-1][k]*j
            if k > 0:
                DP[i][j][k] += DP[i][j+1][k-1]*k
            DP[i][j][k] /= (i+j+k)
print(DP[a][b][c])


### FIXED CODE ###

n = int(input())
*A, = map(int, input().split())
a, b, c = A.count(1), A.count(2), A.count(3)
DP = [[[0.0 for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]
for k in range(c+1):
    for j in range(b+c-k+1):
        for i in range(n-j-k+1):
            if i+j+k == 0:
                continue
            tmp = n
            if i > 0:
                tmp += DP[i-1][j][k]*i
            if j > 0:
                tmp += DP[i+1][j-1][k]*j
            if k > 0:
                tmp += DP[i][j+1][k-1]*k
            DP[i][j][k] = tmp/(i+j+k)
print(DP[a][b][c])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(M)]
AB.reverse()
par=list(range(1,N+1))
size=[1]*N

ans=[(N-1)*N//2]*M

def spar(n):
  if par[n-1]==n:
    return n
  else:
    return spar(par[n-1])

for i in range(0,M-1):
  A,B=AB[i]
  pa,pb=spar(par[A-1]),spar(par[B-1])
  if pa==pb:
    ans[i+1]=ans[i]
  else:
    ans[i+1]=ans[i]-size[pa-1]*size[pb-1]
    sa,sb=size[pa-1],size[pb-1]
    size[pa-1]+=sb
    size[pb-1]+=sa
  par[pa-1]=pa
  par[pb-1]=pa
  
for i in reversed(ans):
  print(i)

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(M)]
AB.reverse()
par=list(range(1,N+1))
size=[1]*N

ans=[(N-1)*N//2]*M

def spar(n):
  if par[n-1]==n:
    return n
  else:
    par[n-1]=spar(par[n-1])
    return par[n-1]

for i in range(0,M-1):
  A,B=AB[i]
  pa,pb=spar(par[A-1]),spar(par[B-1])
  if pa==pb:
    ans[i+1]=ans[i]
  else:
    ans[i+1]=ans[i]-size[pa-1]*size[pb-1]
    sa,sb=size[pa-1],size[pb-1]
    size[pa-1]+=sb
    size[pb-1]+=sa
  par[pa-1]=pa
  par[pb-1]=pa
  
for i in reversed(ans):
  print(i)
### BUGGY CODE ###

S = input()
N = len(S)
i = 0
T = ""
while i <= N-2:
    if S[i] == 'B' and S[i+1] == 'C':
        T += 'D'
        i += 1
    else:
        T += S[i]
    i += 1


N = len(T)
substring = []
l = 0
while l < N:

    if T[l] == 'B' or T[l] == 'C':
        l += 1
        continue
    
    r = l
    tmp = ''
    while r < N and (T[r] == 'A' or T[r] == 'D'):
        tmp += T[r]
        r += 1
    substring.append(tmp)
    if r == N:
        break
    else:
        l = r+1

ans = 0
for s in substring:
    M = len(s)
    D_count = [0]*(M+1)
    for i in range(M-1, -1, -1):
        D_count[i] = D_count[i+1]
        if s[i] == 'D':
            D_count[i] += 1
    
    for i in range(M):
        if T[i] == 'A':
            ans += D_count[i]

print(ans)





### FIXED CODE ###

S = input()
N = len(S)
i = 0
T = []
while i <= N-2:
    if S[i] == 'B' and S[i+1] == 'C':
        T.append('D')
        i += 1
    else:
        T.append(S[i])
    i += 1

T = "".join(T)

N = len(T)
ans = 0
l = 0
while l < N:

    if T[l] == 'B' or T[l] == 'C':
        l += 1
        continue
    
    r = l
    tmp = []
    while r < N and (T[r] == 'A' or T[r] == 'D'):
        tmp.append(T[r])
        r += 1
    
    M = len(tmp)
    D_count = [0]*(M+1)
    for i in range(M-1, -1, -1):
        D_count[i] = D_count[i+1]
        if tmp[i] == 'D':
            D_count[i] += 1
    
    for i in range(M):
        if tmp[i] == 'A':
            ans += D_count[i]
    
    if r == N:
        break
    else:
        l = r+1

print(ans)