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

class Group:
    
    def __init__(self, a, b):
        self.member = {a, b}
        self.n = 2
        
        
N, M = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]

d = {}
ans = [None] * M
ans[-1] = sum([i for i in range(1, N)])
pre = ans[-1]
count = -2
for a, b in AB[:0:-1]:
    now = pre
    if a in d:
        if b in d:
            group1, group2 = d[a], d[b]
            if group1 is group2:
                pass
            else:
                now -= group1.n * group2.n
                group1.member |= group2.member
                group1.n += group2.n
                for x in group2.member:
                    d[x] = group1
        else:
            group = d[a]
            now -= group.n
            group.member.add(b)
            group.n += 1
            d[b] = group
    elif b in d:
        group = d[b]
        now -= group.n
        group.member.add(a)
        group.n += 1
        d[a] = group
    else:
        group = Group(a, b)
        d[a] = group
        d[b] = group
        now -= 1
    ans[count] = now
    pre = now
    count -= 1
for ans_ in ans:
    print(ans_)

### FIXED CODE ###

class Group:
    
    def __init__(self, a, b):
        self.member = {a, b}
        self.n = 2
        
        
N, M = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]

d = {}
ans = [None] * M
ans[-1] = (N - 1) * N // 2
pre = ans[-1]
count = -2
for a, b in AB[:0:-1]:
    now = pre
    if a in d:
        if b in d:
            group1, group2 = d[a], d[b]
            if group1 is group2:
                pass
            else:
                if group1.n < group2.n:
                    group1, group2 = group2, group1
                now -= group1.n * group2.n
                group1.member |= group2.member
                group1.n += group2.n
                for x in group2.member:
                    d[x] = group1
        else:
            group = d[a]
            now -= group.n
            group.member.add(b)
            group.n += 1
            d[b] = group
    elif b in d:
        group = d[b]
        now -= group.n
        group.member.add(a)
        group.n += 1
        d[a] = group
    else:
        group = Group(a, b)
        d[a] = group
        d[b] = group
        now -= 1
    ans[count] = now
    pre = now
    count -= 1
print("\n".join(map(str, ans)))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


from functools import lru_cache

@lru_cache(maxsize=None)
def binbin(binn):
    return bin(binn).count("1")


@lru_cache(maxsize=None)
def popcount(n):
    if n == 0:
        return 0
    return 1 + popcount(n % binbin(n))

def main():
    N = int(input())
    X = input().strip()


    x = int(X, 2)
    xc = binbin(x)
    for i in range(N):
        if X[i] == '0':
            print(popcount(x + (2 ** (N - i - 1))))
        else:
            print(popcount(x - (2 ** (N - i - 1))))



    

if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def binbin(binn):
    return bin(binn).count("1")


def popcount(n):
    if n == 0:
        return 0
    return 1 + popcount(n % binbin(n))


def main():
    N = int(input())
    X = input().strip()

    x1 = 0
    xc = binbin(int(X, 2))
    if xc == 1:
        x2 = -1
    else:
        x2 = 0
    for i in range(N):
        if X[-1 - i] == '1':
            x1 += pow(2, i, xc + 1)
            if x2 != -1:
                x2 += pow(2, i, xc - 1)
    for i in range(N):
        if X[i] == '0':
            print(1 + popcount((x1 + pow(2, N - i - 1, xc + 1)) % (xc + 1)))
        else:
            if x2 == -1:
                print(0)
            else:
                print(1 + popcount((x2 - pow(2, N - i - 1, xc - 1) + xc - 1) % (xc - 1)))


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

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

t = [0]*Q
d = [0]*Q
for q in range(Q):
    t[q],d[q] = map(str, input().split())

mas = [0]*N
for n in range(N):
    mas[n] = S[n]
cnt = [1]*N

for q in range(Q):
    if d[q] == 'L':
        for n in range(N):
            if mas[n] == t[q]:
                if n == 0:
                    cnt[n] = 0
                else:
                    cnt[n-1] += cnt[n]
                    cnt[n] = 0 
    else:
        for n in reversed(range(N)):
            if mas[n] == t[q]:
                if n == N-1:
                    cnt[n] = 0
                else:
                    cnt[n+1] += cnt[n]
                    cnt[n] = 0

ans = 0
for n in range(N):
    ans += cnt[n]
print(ans)

### FIXED CODE ###

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

t = [0]*Q
d = [0]*Q
for q in range(Q):
    t[q],d[q] = map(str, input().split())


s1 = 0
sN = N-1

for q in reversed(range(Q)):
    if t[q] == S[s1] and d[q] == 'L':
        s1 += 1
    elif s1 > 0:
        if d[q] == 'R' and S[s1-1] == t[q]:
            s1 -= 1
    if t[q] == S[sN] and d[q] == 'R':
        sN -= 1
    elif sN < N-1:
        if d[q] == 'L' and S[sN+1] == t[q]:
            sN += 1
    if s1 > sN:
        break
    #print(s1,sN)


print(sN-s1+1)
### BUGGY CODE ###

n,a=int(input()),list(map(int,input().split()))
c=[0]*3
for i in a:c[i-1]+=1
x=[1/i for i in range(1,n+1)]
dp=[[[0]*(n+2) for i in range(n+2)]for i in range(n+2)]
for k in range(n+1):
  for j in range(n+1):
    for i in range(n+1):
      if not n+1>i+j+k>0:continue
      p=n
      if i>0:p+=dp[i-1][j][k]*i
      if j>0:p+=dp[i+1][j-1][k]*j
      if k>0:p+=dp[i][j+1][k-1]*k
      dp[i][j][k]=p*x[i+j+k-1]
print(dp[c[0]][c[1]][c[2]])

### FIXED CODE ###

n,a=int(input()),map(int,input().split());c=[0]*3
for i in a:c[i-1]+=1
x,y,z=c;dp=[[[None]*(z+2) for i in range(n-x+2)]for i in range(n+2)];dp[0][0][0]=0
for k in range(z+1):
  for j in range(n-x-k+1):
    for i in range(n-k-j+1):
      if i+j+k:dp[i][j][k]=((dp[i-1][j][k]*i if i else 0)+(dp[i+1][j-1][k]*j if j else 0)+(dp[i][j+1][k-1]*k if k else 0)+n)/(i+j+k)
print(dp[x][y][z])
### BUGGY CODE ###

def main():
    k = int(input())
    tmp = 7
    mul = 1
    p = 1
    while p < 10**7 and tmp % k != 0:
        mul *= 10
        tmp += 7 * mul
        mul %= k
        tmp %= k
        p += 1
    if tmp % k == 0:
        print(p)
    else:
        print(-1)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    k = int(input())
    tmp = 7
    mul = 1
    p = 1
    while p < 10**7 and tmp % k != 0:
        mul *= 10
        tmp += 7 * mul
        mul %= k
        tmp %= k
        p += 1
    if tmp % k == 0:
        print(p)
    else:
        print(-1)

if __name__ == "__main__":
    main()
### BUGGY CODE ###


def main():
    N, K = map(int, input().split(' '))
    
    # out = min(float('inf'), N)
    prev = N
    
    isFinish = False
    
    if N % K == 0:
        print(0)
        return
    
    while not isFinish:
        next = abs(prev - K)
        
        if next >= prev:
            isFinish = True
        else:
            prev = next
            
    print(prev)

main()

### FIXED CODE ###


def main():
    N, K = map(int, input().split(' '))
    
    # out = min(float('inf'), N)
    prev = N % K
    
    isFinish = False
    
    if prev == 0:
        print(0)
        return
    
    while not isFinish:
        next = abs(prev - K)
        
        if next >= prev:
            isFinish = True
        else:
            prev = next
            
    print(prev)

main()
### BUGGY CODE ###

def solve():
  N, K = map(int, input().split())
  A = [int(i) for i in input().split()]
  F = [int(i) for i in input().split()]

  rest = sum(A) - K
  cost = 0

  while True:
    if rest <= 0: return cost
    cost += 1
    rest -= len([0 for f in F if cost % f == 0])

print(solve())


### FIXED CODE ###

import numpy as np

def solve():
  N, K = map(int,input().split())
  A = np.array(input().split(), np.int64)
  F = np.array(input().split(), np.int64)

  A.sort()
  F.sort()
  F=F[::-1]
  a_sum = A.sum()
  low, high = -1, 10**13

  while low + 1 < high:
      mid = (low + high) // 2
      if np.minimum(A, mid // F).sum() >= a_sum - K:
          high = mid
      else:
          low = mid
  return high

print(solve())
### BUGGY CODE ###

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

num = []
for i in range(n):
  num.append(i+1)

WA = 0
AC = 0

import numpy as np

ar = np.zeros((n, 2), dtype=np.int64)

for i in range(m):
  text = input().strip().split()
  p = int(text[0])
  s = text[1]
  
  if p in num:
    if s == 'AC':
      ar[p-1][1] = 1
      num.remove(p)
    elif s == 'WA':
      ar[p-1][0] += 1
      
for i in range(n):
  if ar[i][1] == 1:
    AC += 1
    WA += ar[i][0]
    
print(AC, WA)

### FIXED CODE ###

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

num = [0]*n
nn = [-1]*n
WA = 0
AC = 0

for i in range(m):
  text = input().strip().split()
  p = int(text[0])
  s = text[1]
  
  if nn[p-1] == -1:
    if s == 'AC':
      AC += 1
      WA += num[p-1]
      nn[p-1] = 1
    elif s == 'WA':
      num[p-1] += 1
      
print(AC, WA)
### BUGGY CODE ###

list_input = [int(n) for n in input().split()]

N = list_input[0]
K = list_input[1]

while N > abs(N - K):
    N = abs(N - K)

print(N)


### FIXED CODE ###

list_input = [int(n) for n in input().split()]

N = list_input[0]
K = list_input[1]

while N > abs(N - K):
    if N >= K:
        N = N % K
    else:
        N = K - N
print(N)
### BUGGY CODE ###

import math
import fractions
 
 
def calc_lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
 
 
if __name__ == '__main__':
    n, m = list(map(int, input().split()))
    a = list(map(lambda x: int(x)//2, input().split()))
    a = list(set(a))
 
    while True:
        odd_flag = 0
        even_flag = 0
        for i in range(len(a)):
            if a[i] % 2 == 0:
                a[i] = a[i] / 2
                even_flag = 1
                if odd_flag == 1:
                    print(0)
                    exit()
            else:
                odd_flag = 1
                if even_flag == 1:
                    print(0)
                    exit()
 
        if even_flag == 0:
            break
        elif odd_flag == 0:
            m = m // 2
 
    lcm = a[0]
    for i in a:
        lcm = calc_lcm(lcm, i)
 
    print(math.ceil((m//lcm)/2))

### FIXED CODE ###

from fractions import gcd
from functools import reduce
import sys
sys.setrecursionlimit(10 ** 7)

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


if __name__ == '__main__':
    n, m = list(map(int, input().split(" ")))
    a = list(map(int, input().split(" ")))
    a = list(set(a))

    # for j in a:
    #     if j % 2 != 0:
    #         print("0")

    # a = [i/2 for i in a]
    l = lcm_list(a)

    # if l == 0:
    #     print(0)
    #     exit()

    if (2 * m) < l:
        print("0")
        exit()

    i = l / 2

    for j in a:
        if i // (j // 2) % 2 == 0:
            print(0)
            exit()

    # if m < i:
    #     print("0")
    else:
        # print("1")
        print(int(((m - i) // l) + 1))
        # print(int((m // i + 1) // 2))
### BUGGY CODE ###

from collections import defaultdict
N, S = map(int, input().split())
A = tuple(map(int, input().split()))

mod = 998244353
U = 3000

pow2 = [1] * (U + 1)
for i in range(1, U + 1):
    pow2[i] = pow2[i - 1] * 2 % mod

dp = defaultdict(int)
dp[(0, 0)] = 1
ans = 0
for a in A:
    newDP = defaultdict(int)
    for (sm, cnt), v in dp.items():
        # 追加しない
        newDP[(sm, cnt)] += v
        newDP[(sm, cnt)] %= mod
        # 追加する
        newDP[(sm+a, cnt + 1)] += v
        newDP[(sm+a, cnt + 1)] %= mod
    dp = newDP

ans = 0
for i in range(N + 1):
    ans = (ans + pow2[N - i] * dp[(S, i)]) % mod
print(ans)

### FIXED CODE ###

import numpy as np
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
fft = np.fft.rfft
ifft = np.fft.irfft
mod = 998244353

N, S = map(int, input().split())
A = list(map(int, input().split()))
U = 3003

dp = np.zeros(U+10, dtype=np.int64)
dp[0] = 1
for a in A:
    newDP = dp.copy() * 2
    newDP[a:] += dp[:-a]
    newDP %= mod
    dp = newDP

print(dp[S])
### BUGGY CODE ###

import bisect
n = int(input())
color = [int(input())]
for i in range(1,n):
    num = int(input())
    if min(color) >= num:
        color.append(num)
    else:
        color = sorted(color)
        bis = bisect.bisect_left(color, num)
        color[bis-1] = num
print(len(color))


### FIXED CODE ###

import bisect
from collections import deque
n = int(input())
color = deque([int(input())])
for i in range(1,n):
    num = int(input())
    if color[0] >= num:
        color.appendleft(num)
    else:
        bis = bisect.bisect_left(color, num)
        color[bis-1] = num
print(len(color))
### BUGGY CODE ###

import sys

N,K=map(int,input().split())
ZET=N
b=(10**18)
c=N
b1=N
for i in range(int(b)):
  if K==1:
    b1=0
    break
  c=abs(b1-K)
  if int(b)<c:
    break
  b1=c
  b=c
print(b1)

### FIXED CODE ###

import sys

N,K=map(int,input().split())
ZET=N
b=(10**18)
c=N
b1=N
for i in range(int(b)):
  if K==1:
    b1=0
    break
  if N>10**17 and K<10**9:
    b1=N%K
    c=abs(b1-K)
    if b1>c:
      b1=c
    break
  c=abs(b1-K)
  if int(b)<=c:
    break
  b1=c
  b=c
print(b1)
### BUGGY CODE ###

def solve():
    n = int(input())
    s = [sorted(input()) for _ in range(n)]
    cnt = 0
    for i in range(n-1):
        for j in range(i+1, n):
            if s[i] == s[j]:
                cnt += 1
    print(cnt)
    return 0

if __name__ == "__main__":
    solve()


### FIXED CODE ###

import math
import collections
import fractions
import itertools
import functools
import  operator

def solve():
    n = int(input())
    s = ["".join(sorted(input())) for _ in range(n)]
    cnt = 0
    past = {}
    for i in range(n):
        si = s[i]
        if si in past:
            past[si] += 1
        else:
            past[si] = 1
    for i in past.values():
        cnt += i*(i-1)//2
    print(cnt)
    return 0

if __name__ == "__main__":
    solve()
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
if n%2==1:
    if a.count(0)==1 and all(a.count(2*i)==2 for i in range(1,n//2+1)):print(2**(n//2)%(10**9+7))
    else: print(0)
else:
    if all(a.count(2*i+1)==2 for i in range(n//2)):print(2**(n//2)%(10**9+7))
    else: print(0)

### FIXED CODE ###

n=int(input())
a=sorted(list(map(int,input().split())))
if n%2==1:
    if a[0]==0 and all(a[i]==2*((i+1)//2) for i in range(1,n)):print(2**(n//2)%(10**9+7))
    else: print(0)
else:
    if all(a[i]==2*(i//2)+1 for i in range(n)):print(2**(n//2)%(10**9+7))
    else: print(0)
### BUGGY CODE ###

from itertools import combinations
from fractions import gcd
N = int(input())
A = list(map(int,input().split()))

comb = list(combinations(A,len(A)-1))
max_gcd = 0
for i in range(len(comb)):
  temp_gcd = comb[i][0]
  for j in range(1,len(comb[i])):
    temp_gcd = gcd(temp_gcd,comb[i][j])
    if temp_gcd < max_gcd:
      break
  max_gcd = max(max_gcd,temp_gcd)

print(max_gcd)

### FIXED CODE ###

from fractions import gcd
N = int(input())
A = list(map(int,input().split()))

L = [0]
R = [0]
for i in range(N-1):
  L.append(gcd(L[i],A[i]))
  R.append(gcd(R[i],A[-i-1]))

max_gcd = 0
for i in range(N):
  max_gcd = max(max_gcd, gcd(L[i],R[-i-1]))

print(max_gcd)
### BUGGY CODE ###

# 1(黒マス)を探す
import numpy as np
h, w = [int(item) for item in input().split(" ")]
a = np.zeros((h,w), dtype=int)
for i in range(h):
    tmp = [0 if item=="." else 1 for item in input()]
    a[i] = tmp
    
def one(a):
    n = len(a)
    b = np.zeros((n,), dtype=int)
    c = np.zeros((n,), dtype=int)
    out = np.zeros((n,), dtype=int)
    out2 = np.zeros((n,), dtype=int)
    out[:] = -1
    out2[:] = -1
    last = -1
    for i,item in enumerate(a):
        if item==1:
            last = i
        b[i] = last
    last = -1
    for i in reversed(range(n)):
        item = a[i]
        if item==1:
            last = i
        c[i] = last
    b[b==-1] = n+2
    c[c==-1] = n+2
    out[b!=-1] = b[b!=-1]
    out2[c!=-1] = c[c!=-1]
    dist = np.abs(np.arange(n) - out)
    dist[out==n+2] = n+2
    dist2 = np.abs(np.arange(n) - out2)
    dist2[out2==n+2] = n+2
    return np.where(dist<dist2, dist, dist2)    
def one2(a):
    dist = np.zeros((a.shape[0], ), dtype=int)
    dist2 = np.zeros((a.shape[0], ), dtype=int)
    last = 0
    lastd = a[0]
    for i, item in enumerate(a):
        if a[i] < (i-last)+lastd:
            v = a[i]
            last = i
            lastd = a[i]
        else:
            v = (i - last) + lastd
        dist[i] = v
    last = len(a)-1
    lastd = a[-1]
    for i in reversed(range(len(a))):
        item = a[i]
        if a[i] < (last-i)+lastd:
            v = a[i]
            last = i
            lastd = a[i]
        else:
            v = (last-i) + lastd
        dist2[i] = v
    return np.where(dist<dist2, dist, dist2)
def two(a):
    out = np.zeros(a.shape, dtype=int)
    for i in range(a.shape[0]):
        out[i] = one(a[i])
    for j in range(a.shape[1]):
        tmp = one(a[:,j])
        tmp2 = one2(out[:,j])
        out[:,j] = np.where(tmp<tmp2, tmp, tmp2)
    return out

print(np.max(two(a)))

### FIXED CODE ###

# AGC033A

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w = map(int, input().split())
s = [None] * h
for i in range(h):
    s[i] = input()

r = h
c = w
ds = [[10**15]*c for _ in range(r)]
for i in range(r):
    prev = -1
    for j in range(c):
        if s[i][j]=="#":
            prev = j
        if prev>=0:
            ds[i][j] = j-prev
    prev = -1
    for j in range(c-1,-1,-1):
        if s[i][j]=="#":
            prev = j
        if prev>=0:
            ds[i][j] = min(ds[i][j], prev-j)
for j in range(c):
    prev = -1
    prevind = -1
    for i in range(r):
        if prev<0 or ds[i][j]<prev+(i-prevind):
            prev = ds[i][j]
            prevind = i
        if prev>=0:
            ds[i][j] = min(ds[i][j], prev+(i-prevind))
    prev = -1
    prevind = -1
    for i in range(r-1, -1, -1):
        if prev<0 or ds[i][j]<prev+(prevind-i):
            prev = ds[i][j]
            prevind = i
        if prev>=0:
            ds[i][j] = min(ds[i][j], prev+(prevind-i))
print(max(max(item) for item in ds))
### BUGGY CODE ###

import sys

input = sys.stdin.readline


# https://atcoder.jp/contests/agc039/submissions/7878237
class AtCoder:
    def main(self):
        N = int(input())
        X = input().rstrip()

        k_cycles = 0
        ans = 0
        L = []
        for k in self.make_divisors(N):
            if (N // k) % 2 != 0:
                first_k_bit = X[:k]
                first_k_bit_ = first_k_bit.replace("0", "2").replace("1", "0").replace("2", "1")
                check_target = first_k_bit + (first_k_bit_ + first_k_bit) * ((N // k - 1) // 2)
                k_cycle = int(first_k_bit, 2) + (int(check_target, 2) <= int(X, 2))

                for l, cnt in L:
                    if k % l == 0:
                        k_cycle -= cnt
                L.append((k, k_cycle))

                k_cycles += k_cycle
                ans += 2 * k * k_cycle

        ans += (int(X, 2) + 1 - k_cycles) * 2 * N

        print(ans % 998244353)

    def make_divisors(self, n: int):
        divisors = []
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                divisors.append(i)
                if i != n // i:
                    divisors.append(n // i)

        divisors.sort()
        return divisors


# Run main
if __name__ == '__main__':
    AtCoder().main()


### FIXED CODE ###

import sys

input = sys.stdin.readline


# https://atcoder.jp/contests/agc039/submissions/7878237
class AtCoder:
    def main(self):
        N = int(input())
        X = input().rstrip()

        k_cycles = 0
        ans = 0
        L = []
        for k in self.make_divisors(N):
            if (N // k) % 2 != 0:
                first_k_bit = X[:k]
                first_k_bit_ = first_k_bit.replace("0", "2").replace("1", "0").replace("2", "1")
                check_target = first_k_bit + (first_k_bit_ + first_k_bit) * ((N // k - 1) // 2)
                k_cycle = int(first_k_bit, 2) + (int(check_target, 2) <= int(X, 2))

                for l, cnt in L:
                    if k % l == 0:
                        k_cycle -= cnt
                L.append((k, k_cycle))

                k_cycles += k_cycle
                ans += 2 * k * k_cycle

        ans += (int(X, 2) + 1 - k_cycles) * 2 * N

        print(ans % 998244353)

    def make_divisors(self, n: int):
        divisors = []
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                divisors.append(i)
                if i != n // i:
                    divisors.append(n // i)

        divisors.sort()
        return divisors


# Run main
if __name__ == '__main__':
    AtCoder().main()
### BUGGY CODE ###

from bisect import bisect
from sys import stdin


def main():
    input = lambda: stdin.readline()[:-1]
    N = int(input())
    S = input()

    rgb = {'R': [], 'G': [], 'B': []}
    for i, s in enumerate(S):
        rgb[s].append(i)

    def count_(s1, s2):
        ret = 0
        x = bisect(rgb[s1], i)
        for j in rgb[s1][x:]:
            y = bisect(rgb[s2], j)
            d = j - i
            if j + d < N and S[j+d] == s2:
                ret += len_[s2] - y - 1
            else:
                ret += len_[s2] - y
        return ret

    ans = 0
    len_ = {'R': len(rgb['R']), 'G': len(rgb['G']), 'B': len(rgb['B'])}
    for i, s in enumerate(S):
        if s == 'R':
            for s1, s2 in (('G', 'B'), ('B', 'G')):
                ans += count_(s1, s2)
        elif s == 'G':
            for s1, s2 in (('R', 'B'), ('B', 'R')):
                ans += count_(s1, s2)
        else:
            for s1, s2 in (('R', 'G'), ('G', 'R')):
                ans += count_(s1, s2)
    print(ans)


main()


### FIXED CODE ###

from bisect import bisect
from sys import stdin


def main():
    input = lambda: stdin.readline()[:-1]
    N = int(input())
    S = input()

    rgb = {'R': [], 'G': [], 'B': []}
    for i, s in enumerate(S):
        rgb[s].append(i)

    def count_(s1, s2):
        ret = 0
        x = bisect(rgb[s1], i)
        for j in rgb[s1][x:]:
            y = bisect(rgb[s2], j)
            d = j - i
            if j + d < N and S[j+d] == s2:
                ret += len_[s2] - y - 1
            else:
                ret += len_[s2] - y
        return ret

    ans = 0
    len_ = {'R': len(rgb['R']), 'G': len(rgb['G']), 'B': len(rgb['B'])}
    for i, s in enumerate(S):
        if s == 'R':
            for s1, s2 in (('G', 'B'), ('B', 'G')):
                ans += count_(s1, s2)
        elif s == 'G':
            for s1, s2 in (('R', 'B'), ('B', 'R')):
                ans += count_(s1, s2)
        else:
            for s1, s2 in (('R', 'G'), ('G', 'R')):
                ans += count_(s1, s2)
    print(ans)


main()
### BUGGY CODE ###

n, y = map(int, input().split())


def main():
    for a in range(n + 1):
        for b in range(n - a + 1):
            for c in range(n - a - b + 1):
                if (a * 1000 + b * 5000 + c * 10000 == y) & (a + b + c == n):
                    return print(c, b, a)
    return print("-1 -1 -1")


main()

### FIXED CODE ###

n, y = map(int, input().split())


def main():
    for a in range(n + 1):
        for b in range(n - a + 1):
            c = n - a - b
            if (a * 1000 + b * 5000 + c * 10000 == y) & (a + b + c == n):
                return print(c, b, a)
    return print("-1 -1 -1")


main()
### BUGGY CODE ###

n=int(input())
s=list(input() for _ in range(n))

t=['']*n

for i in range(n):
	t[i]=sorted(s[i])

u=sorted(t)

cnt=0

for i in range(n-1):    
	for j in range(i+1,n):
		if u[i]!=u[j]:
			break
		else:
			cnt+=1

print(cnt)

### FIXED CODE ###

n=int(input())
s=list(input() for _ in range(n))

t=['']*n

for i in range(n):
	t[i]=sorted(s[i])

u=sorted(t)

cnt=0

#for i in range(n-1):    
#	for j in range(i+1,n):
#		if u[i]!=u[j]:
#			break
#		else:
#			cnt+=1

cnt_a=0
cnt_b=0

u.append(['0'])

#print(u)


for i in range(n):
	if u[i+1]==u[i]:
		cnt_a+=1
		#print(cnt_a)
	else:
		if cnt_a>0:
			cnt_b+=(cnt_a+1)*cnt_a//2
			#print(cnt_b)
			cnt_a=0

print(cnt_b)