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

import sys
input = sys.stdin.readline

class Unionfind:
     
    def __init__(self,n):
        self.uf = [-1]*n
 
    def find(self,x):
        if self.uf[x] < 0:
            return x
        else:
            self.uf[x] = self.find(self.uf[x])
            return self.uf[x]
 
    def same(self,x,y):
        return self.find(x) == self.find(y)
 
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.uf[x] > self.uf[y]:
            x,y = y,x
        self.uf[x] += self.uf[y]
        self.uf[y] = x
        return True
 
    def size(self,x):
        x = self.find(x)
        return -self.uf[x]

def main():
    n = int(input())
    xy = [list(map(int,input().split())) for i in range(n)]
    xy2 = [[x[0],x[1],i] for (i,x) in enumerate(xy)]
    xy2.sort()
    u = Unionfind(n)

    s = set()
    for i,X in enumerate(xy2):
        x,y,ind = X
        check = True
        cand = []
        mi = -1
        count = n+5
        for j in s:
            if y > xy[j][1]:
                check = False
                u.union(ind,j)
                cand.append(j)
                if count > xy[j][1]:
                    count = xy[j][1]
                    mi = j
            
        if check:
            s.add(ind)
        else:
            for j in cand:
                if j == mi:
                    continue
                s.remove(j)
    for i in range(n):
        print(u.size(i))

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

class Unionfind:
     
    def __init__(self,n):
        self.uf = [-1]*n
 
    def find(self,x):
        if self.uf[x] < 0:
            return x
        else:
            self.uf[x] = self.find(self.uf[x])
            return self.uf[x]
 
    def same(self,x,y):
        return self.find(x) == self.find(y)
 
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.uf[x] > self.uf[y]:
            x,y = y,x
        self.uf[x] += self.uf[y]
        self.uf[y] = x
        return True
 
    def size(self,x):
        x = self.find(x)
        return -self.uf[x]

def main():
    n = int(input())
    xy = [list(map(int,input().split())) for i in range(n)]
    xy2 = [[x[0],x[1],i] for (i,x) in enumerate(xy)]
    xy2.sort()
    u = Unionfind(n)

    l = []
    for x,y,ind in xy2:
        M = y
        le = ind
        while l and xy[l[-1]][1] < y:
            v = l.pop()
            if M > xy[v][1]:
                M = xy[v][1]
                le = v
            u.union(ind,v)
        l.append(le)
    for i in range(n):
        print(u.size(i))

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

n = int(input())
a = [[] for i in range(n)]
for i in range(n):
    a[i] = list(map(int,input().split()))
    for j in range(n-1):
        a[i][j] -= 1
    a[i].reverse()
q = []

def check(i):
    if len(a[i]) == 0:
        return 
    j = a[i][-1]
    if len(a[j]) == 0:
        return
    if a[j][-1] == i:
        q.append([min(i,j), max(i,j)])
def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

for i in range(n):
    check(i)
day = 0
while (len(q) > 0):
    day += 1
    prevQ = q.copy()
    prevQ = get_unique_list(prevQ)
    q = []
    for i,j in prevQ:
        a[i].pop()
        a[j].pop()
    for i,j in prevQ:
        check(i)
        check(j)
for i in range(n):
    if len(a[i]) > 0:
        print(-1)
        exit()
print(day)

### FIXED CODE ###

n = int(input())
a = [[] for i in range(n)]
for i in range(n):
    a[i] = list(map(int,input().split()))
    for j in range(n-1):
        a[i][j] -= 1
    a[i].reverse()
q = []

def check(i):
    if len(a[i]) == 0:
        return 
    j = a[i][-1]
    if len(a[j]) == 0:
        return
    if a[j][-1] == i:
        q.append([min(i,j), max(i,j)])
for i in range(n):
    check(i)
day = 0
while (len(q) > 0):
    day += 1
    prevQ = list(map(list, set(map(tuple, q))))
    q = []
    for i,j in prevQ:
        a[i].pop()
        a[j].pop()
        check(i)
        check(j)
for i in range(n):
    if len(a[i]) > 0:
        print(-1)
        exit()
print(day)
### BUGGY CODE ###

import copy
n=int(input())
box=list(map(int,input().split()))
box_sort=sorted(box)
for i in box:
    ano_box=copy.copy(box_sort)
    ano_box.remove(i)
    print(ano_box[n//2-1])

### FIXED CODE ###

n=int(input())
x=list(map(int,input().split()))
y=sorted(x)
xr,xl=y[n//2],y[n//2-1]
for i in x:
    print(xr if i<=xl else xl)
### BUGGY CODE ###

S=input()
Q=int(input())
words=[]
for a in range(Q):
    A=input().split()
    words.append(A)
left=[]
right=[]
number=0
for a in words:
    if a[0]=='1':
        number+=1
    else:
        if number%2==0:
            if a[1]=='1':
                left.insert(0,a[2])
            else:
                right.append(a[2])
        else:
            if a[1]=='1':
                right.append(a[2])
            else:
                left.insert(0,a[2])
T=[a for a in S]
if number%2==0:
    kotae=left+T+right
    moji=''
    for a in kotae:
        moji+=a
    print(moji)
else:
    left.reverse()
    T.reverse()
    right.reverse()
    kotae = right+T+left
    moji = ''
    for a in kotae:
        moji += a
    print(moji)
    

### FIXED CODE ###

from collections import deque
S=input()
Q=int(input())
words=[]
for a in range(Q):
    A=input().split()
    words.append(A)
T=[a for a in S]
answers=deque(T)
number=0
for a in words:
    if a[0]=='1':
        number+=1
    else:
        if number%2==0:
            if a[1]=='1':
                answers.appendleft(a[2])
            else:
                answers.append(a[2])
        else:
            if a[1]=='1':
                answers.append(a[2])
            else:
                answers.appendleft(a[2])
if number%2==0:
    kotae=list(answers)
    moji=''
    for a in kotae:
        moji+=a
    print(moji)
else:
    kotae = list(answers)
    kotae.reverse()
    moji = ''
    for a in kotae:
        moji += a
    print(moji)
### BUGGY CODE ###

N,K=map(int,input().split())
H=list(map(int,input().split()))
cost =200000
DP=[0]*(N+10)
DP[0]=0
DP[1]=abs(H[1]-H[0])
for i in range(2,N):
  DP[i]=min([abs(H[i]-H[k])+DP[k] for k in range(max(i-K,0),i)])
print(DP[N-1])

### FIXED CODE ###

def a():
    N, K = [int(n) for n in input().split()]
    h = [int(n) for n in input().split()]
    # dp[i]はi番目までたどり着くのに必要な最小コスト
    # dp[0] = 0
    # dp[1] = |h[1] - h[0]|
    # dp[i] = min(dp[0]+h[i]-h[0], dp[1]+h[i]-h[1], ...)
    dp = [0] * N
    dp[0] = 0
    dp[1] = abs(h[1] - h[0])
    for i in range(2, N):
        dp[i] = min([dp[k] + abs(h[k] - h[i]) for k in range(max(i - K, 0), i)])
    print(dp[N-1])
 
if __name__ == "__main__":
    a()
### BUGGY CODE ###

N = int(input())
flg = True
while(flg):
    for a in range(0,N):
        for b in range(0,N):
            total = 4*a + 7*b
            if total == N:
                flg = False
                break
if(flg):
    print('No')
else:
    print('Yes')

### FIXED CODE ###

N = int(input())
res = 0
for a in range (0,N//4 + 1):
    for b in range(0,N//7 + 1):
        total = 4 * a + 7 * b
        if total == N:
            res += 1
if res > 0:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

loop = int(input())
num_list = list(map(int, input().split()))
before = []
ans = 0
for n in num_list:
  flg = True
  for m in before:
    if m < n:
      flg = False
      break
  before.append(n)
  if flg:
    ans += 1
print(ans)

### FIXED CODE ###

loop = int(input())
num_list = list(map(int, input().split()))
ans = 0
min_value = 20000000
for n in num_list:
  flg = True
  if min_value < n:
    flg = False
  else:
    min_value = n
  if flg:
    ans += 1
print(ans)
### BUGGY CODE ###

import collections
n = int(input())
s = input()
ans = 10**6
for i in range(len(s)):
    x = collections.Counter(s[:i])
    y = collections.Counter(s[i+1:len(s)])
    ans = min(ans,x["W"]+y["E"])
print(ans)

### FIXED CODE ###

import numpy
n = int(input())
s = input()
a = [0]*n
ans = 10**6
for i in range(n):
    if s[i] == 'W':
        a[i] = 1
res = numpy.cumsum(a)
for i in range(n):
    x = res[i]-str(a[i]).count('1')
    y = n-i-1-(res[n-1]-res[i])
    ans = min(ans,x+y)
print(ans)
### BUGGY CODE ###

S = input()
i = 0
ans = 0
for j in range(3, len(S)+1):
    for i in range(len(S)):
        if j-i < 4:
            continue
        if int(S[i:j]) % 2019 == 0:
            ans += 1
print(ans)

### FIXED CODE ###

S = input()
mod_bucket = [0] * 2019
mod_bucket[0] = 1
 
_S = S[::-1]
mod = 0
p = 1
for i in range(len(S)):
    mod = (p * int(_S[i]) + mod) % 2019
    mod_bucket[mod] += 1
    p = p*10%2019

ans = sum([mod*(mod-1)/2 for mod in mod_bucket])
print(int(ans))
### BUGGY CODE ###

from collections import deque
n,m=map(int,input().split())
d={i:[] for i in range(1,n+1)}
for i in range(m):
    a,b=map(int,input().split())
    d[a].append(b)
    d[b].append(a)
l=[0 for i in range(n+1)]
q=deque([1])
#print(d)
while len(q)>0:
    x=q.popleft()
    for i in d[x]:
        #print(i)
        if i!=1 and l[i]==0 and x not in q:
            q.append(i)
            #print(i)
            l[i]=str(x)
l=l[2:]
#print(l)
print('No' if 0 in l else 'Yes\n'+'\n'.join(l))


### FIXED CODE ###

from collections import deque
n,m,*inp=map(int,open(0).read().split())
d=[[] for i in range(n)]
for i in range(m):
    j=2*i
    a,b=inp[j:j+2]
    a-=1
    b-=1
    d[a].append(b)
    d[b].append(a)
l=[-1 for i in range(n)]
q=deque([0])
#print(d)
while len(q)>0:
    x=q.popleft()
    for i in d[x]:
        #print(i)
        if l[i]==-1:
            q.append(i)
            #print(i)
            l[i]=str(x+1)
l=l[1:]
#print(l)
print('No' if 0 in l else 'Yes\n'+'\n'.join(l))
### BUGGY CODE ###

import numpy as np

n, k = map(int, input().split())
h = np.array(input().split(), dtype=np.int)
cost = np.array([10 ** 9] * n)
cost[0] = 0
for i in range(n-1):
  cur_h = h[i]
  cur_cost = cost[i]
  for jump in range(1, k + 1):
    if i + jump >= n:
      break
    cost[i+jump] = min(cost[i+jump], cur_cost + abs(cur_h - h[i+jump]))
print(cost[-1])


### FIXED CODE ###

import numpy as np

n, k = map(int, input().split())
h = np.array(input().split(), dtype=np.int)
cost = np.zeros(n, dtype=np.int)
for i in range(1, n):
  cur_h = h[i]
  start = max(0, i - k)
  cost[i] = np.min(cost[start : i] + np.abs(h[start : i] - cur_h))
print(cost[-1])
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
mul=1
for a in A:
    mul*=a
print(mul if mul<=10**18 else -1)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
if 0 in A:
    print(0)
else:
    mul=1
    for a in A:
        mul*=a
        if mul>10**18:
            print(-1)
            exit()
    print(mul)
### BUGGY CODE ###

N=int(input())
p = list(map(int,input().split()))
cnt=0
x=[]
for i in range(N):
    if i==0:
        x+=[p[i]]
        cnt+=1
    else:
        mi = min(x)
        if p[i] <= mi:
            cnt+=1
            x += [p[i]]
        else:
            continue
print(cnt)

### FIXED CODE ###

N=int(input())
p = list(map(int,input().split()))
cnt=0
x=[]
for i in range(N):
    if i==0:
        x=p[i]
        cnt+=1
    else:
        if p[i]<x:
            x=p[i]
        if p[i] <= x:
            cnt+=1
            x = p[i]
        else:
            continue
print(cnt)
### BUGGY CODE ###

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

y=x
A=[]
A.append(y)
cnt=1

for i in range(m):
    y=(y**2)%m
    cnt+=1
    if y in A:
        break
    else:
        A.append(y)

c=A.index(y) #周期のはじめ
d=cnt-(c+1)  #周期のはじめから次の周期のはじめで個数を求める

e=sum(A[:c]) 
#周期に入るまえまでを足しておく

f=0
for w in range((n-c)%d):
    f+=A[c:][w]
    #周期からはみでた最後の部分

g=sum(A[c:])#1周期分
h=g*((n-c)//d)#かけざん

print(e+h+f)

### FIXED CODE ###

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

y=x
A=[]
A.append(y)
cnt=1
su=x

for i in range(m):
    y=(y**2)%m
    cnt+=1
    if y in A:
        break
    else:
        A.append(y)
        su+=y

c=A.index(y) #周期のはじめ
d=cnt-(c+1)  #周期のはじめから次の周期のはじめで個数を求める

e=sum(A[:c]) 
#周期に入るまえまでを足しておく


f=sum(A[c:c+(n-c)%d])
    #周期からはみでた最後の部分

g=su-e#1周期分
h=g*((n-c)//d)#かけざん

print(e+h+f)
### BUGGY CODE ###

N, K = map(int, input().split())
p_list = list(map(int, input().split()))
EV_p_list = [0] * len(p_list)

for i in range(len(p_list)):
  EV_p_list[i] = (p_list[i] + 1) / 2

max_EV = 0
for i in range(N - K + 1):
  tmp = 0
  for j in range(K):
    tmp += EV_p_list[i + j]
  
  if tmp >= max_EV:
    max_EV = tmp

print(max_EV)

### FIXED CODE ###

N, K = map(int, input().split())
p_list = list(map(int, input().split()))
EV_p_list = [0] * len(p_list)

for i in range(len(p_list)):
  EV_p_list[i] = (p_list[i] + 1) / 2

# 最初のsum
sum_EV = 0
for i in range(K):
  sum_EV = sum_EV + EV_p_list[i]

# それ以降の比較
max_EV = sum_EV
for i in range(1, N - K + 1):
  sum_EV = sum_EV - EV_p_list[i - 1] + EV_p_list[i + K - 1]
  if sum_EV > max_EV:
    max_EV = sum_EV

print(max_EV)
### BUGGY CODE ###

import sys

def div(i):
    ans = []
    for d in range(1, i + 1):
        if i % d == 0:
            if d ** 2 > i: break
            if d ** 2 == i: ans.append(d)
            else:
                ans.append(d)
                ans.append(i // d)
    return ans

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    Count = [0] * N
    In = []
    add = 0
    for i in reversed(range(N)):
        if Count[i] % 2 == A[i]: continue
        elif (Count[i] + 1) % 2 == A[i]:
            add += 1
            In.append(i + 1)
            D = div(i + 1)
            for d in D: Count[d - 1] += 1
        else:
            print(-1)
            break
    else:
        print(add)
        print(" ".join(map(str, In)))

    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys

def divisor(N, B):
    i = 1
    d = []
    while i ** 2 <= N:
        if N % i == 0:
            B[i-1] = (B[i-1] + 1) % 2
            if i ** 2 < N: B[N // i - 1] = (B[N//i - 1] + 1) % 2 
        i += 1
    return 0


def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    B = [0] * N
    ans = []
    M = 0

    for i in reversed(range(N)):
        if B[i] != A[i]:
            divisor(i+1, B)
            M += 1
            ans.append(i+1)

    print(M)
    print(" ".join(map(str, ans)))

    return 0

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

N, M = map(int, input().split())
idcard = [[int(j) for j in input().split()] for i in range(M)]
ans = {}
if M == 1:
    print(idcard[0][1] - idcard[0][0] + 1)
    exit()
t = 0
for i in idcard:
    for j in range(i[0], i[1] + 1):
        if j in ans:
            ans[j] += 1
        else:
            ans[j] = 1
        t = max(ans.values())
w = 0
for i in ans.values():
    if i == t:
        w += 1

print(w)

### FIXED CODE ###

N, M = map(int, input().split())
idcard = [[int(j) for j in input().split()] for i in range(M)]

L = 0
R = 10**10
for i in idcard:
    L = max(L, i[0])
    R = min(R, i[1])
if R >= L:
    print(R - L + 1)
else:
    print(0)
### BUGGY CODE ###

import sys
import bisect
import copy
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]
inf = 10**9+1

def dfs(v,prev = -1):
    x = As[v]
    if len(LIS) == 0:
        old = inf
        i = len(LIS)
        LIS.append(x)
    elif x > LIS[-1]:
        old = inf
        i = len(LIS)
        LIS.append(x)
    else:
        i = bisect.bisect_left(LIS, x)
        old = LIS[i]
        LIS[i] = x
    if inf in LIS:
        a = LIS.index(inf)
    else:
        a = len(LIS)
    ans_array[v] = a
    for u in graph[v]:
        if u == prev:
            continue
        dfs(u,v)
    LIS[i] = old

N = int(input())
As = list(map(int,input().split()))
graph = [[] for _ in range(N)]

for i in range(N-1):
    a,b = list(map(int,input().split()))
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
LIS = []
ans_array = [0] * N
dfs(0)
for i in range(N):
    print(ans_array[i])


### FIXED CODE ###

import sys
import bisect
import copy
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]
inf = 10**9+1

def dfs(v,prev = -1):
    x = As[v]
    if len(LIS) == 0 or x > LIS[-1]:
        old = inf
        i = len(LIS)
        LIS.append(x)
    else:
        i = bisect.bisect_left(LIS, x)
        old = LIS[i]
        LIS[i] = x

    a = len(LIS)
    ans_array[v] = a
    for u in graph[v]:
        if u == prev:
            continue
        dfs(u,v)
    if old == inf:
        LIS.pop(-1)
    else:
        LIS[i] = old

N = int(input())
As = list(map(int,input().split()))
graph = [[] for _ in range(N)]

for i in range(N-1):
    a,b = list(map(int,input().split()))
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
LIS = []
ans_array = [0] * N
dfs(0)
for i in range(N):
    print(ans_array[i])
### BUGGY CODE ###

#

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop
import sys
sys.setrecursionlimit(1000000000)

def solve(positions, s, t):
    # print('{}, s = {}, t = {}'.format(positions, s, t))
    if len(t) == 0:
        return 0

    if len(positions[t[0]]) == 0:
        return -1

    i = 0
    j = 0
    while i < len(s) and j < len(t):
        candidates = positions[t[j]]
        pos = bisect.bisect_left(candidates, i)
        if pos == len(candidates):
            break

        i = candidates[pos] + 1
        j += 1

    if j == len(t):
        return i
    else:
        rest = solve(positions, s, t[j:])
        return len(s) + rest if rest != -1 else -1


def main():
    s = input()
    t = input()

    positions = defaultdict(list)
    for i in range(len(s)):
        positions[s[i]].append(i)

    print(solve(positions, s, t))


if __name__ == '__main__':
    main()


### FIXED CODE ###

#

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop


def solve(positions, s, t):

    if not set(t) <= set(s):
        return -1

    loop = 0
    prev = -1

    for tchar in t:
        candidates = positions[tchar]
        pos = bisect.bisect_right(candidates, prev)

        if pos == len(candidates):
            loop += 1
            pos = 0
        prev = candidates[pos]

    return loop * len(s) + prev + 1


def main():
    s = input()
    t = input()

    positions = defaultdict(list)
    for i in range(len(s)):
        positions[s[i]].append(i)

    print(solve(positions, s, t))


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

s = input()
x, y = map(int, input().split())
a = 0
t = [[0], [0]]
n = 0
for i in range(len(s)):
    if s[i] == 'F':
        t[n][-1] += 1
    else:
        n = 1 - n
        t[n].append(0)
flag = [False, False]
z = [x, y]
for k in range(2):
    tt = t[k]
    zk = z[k]
    if k == 0:
        p = [tt[0]]
    else:
        p = [tt[0], -tt[0]]
    if len(tt) > 1:
        for i in tt[1:]:
            pp = []
            for j in p:
                pp.append(j + i)
                pp.append(j - i)
            p = pp
    if zk in p:
        flag = True
    else:
        flag = False
        break
if flag:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

from collections import defaultdict

s = input()
x, y = map(int, input().split())
a = 0
t = [[0], []]
n = 0
for i in range(len(s)):
    if s[i] == 'F':
        t[n][-1] += 1
    else:
        n = 1 - n
        t[n].append(0)
flag = [False, False]
z = [x, y]
for k in range(2):
    tt = t[k]
    zk = z[k]
    if len(tt) == 0:
        if zk == 0:
            flag = True
            continue
        else:
            print(1, k)
            flag = False
            break
    p = sum(tt)
    dp = defaultdict(bool)
    i = 1
    if k == 0:
        dp[tt[0]] = True
    else:
        dp[tt[0]] = True
        dp[-tt[0]] = True
    if len(tt) > 1:
        for tj in tt[1:]:
            dp2 = defaultdict(bool)
            for xj in dp.keys():
                dp2[xj + tj] = True
                dp2[xj - tj] = True
            dp = dp2
    flag = dp[zk]
    if not flag:
        break
if flag:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

a=int(input())
ai=[int(i) for i in input().split()]

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under
c=[ai.count(x) for x in set(ai) if ai.count(x)>1]
val=sum([cmb(x,2) for x in c])
for i in range(len(ai)):
    b=ai.count(ai[i])
    print(val-b+1)

### FIXED CODE ###

import collections
a=int(input())
ai = list(map(int, input().split()))
c = collections.Counter(ai)
val=0
for i in c.values():
    val+=i*(i-1)//2
for i in range(len(ai)):
    b=c[ai[i]]
    print(val-b+1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

N = ii()
S = input()
h = [0]*N

for i, a in enumerate(S):
    if a=='R':
        h[i] = 0
    elif a=='G':
        h[i] = 1
    else:
        h[i] = 9

cnt = -1
ans = 0
for i in range(N):
    cnt = h[i]
    for j in range(i+1, N):
        num = cnt + h[j]
        for k in range(j+1, N):
            if num + h[k] == 10 and k!=2*j-i:
                ans += 1

print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

N = ii()
S = input()
h = [0]*N
h = 'RGB'*1000

#h = h.replace('R', '1').replace('G', '2').replace('B', '7')
'''
cnt = -1
ans = 0
for i in range(N):
    cnt = int(h[i])
    for j in range(i+1, N):
        num = cnt + int(h[j])
        if num == 3 or num == 9 or num==8:
            for k in range(j+1, N):
                if num + int(h[k]) == 10 and k!=2*j-i:
                    ans += 1
'''

#h = h.replace('R', '1').replace('G', '2').replace('B', '7')

c_r = c_g = c_b = 0
h = ''
for i, a in enumerate(S):
    if a == 'R':
        c_r += 1
        h += '1'
    if a == 'G':
        c_g += 1
        h += '2'
    if a == 'B':
        c_b += 1
        h += '7'

ans = c_r * c_g * c_b

for i in range(N):
    for j in range(i+1, N):
        if 2*j-i<N and int(h[i]) + int(h[j]) + int(h[2*j-i]) == 10:
            ans -= 1
print(ans)