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

from math import sqrt
def Divisor_Set(n):
    s = set()
    for i in range(1, int(sqrt(n))+2):
        if n%i == 0:
            s.add(i)
            s.add(n//i)
    return s

def main():
    n = int(input())
    a = list(map(int, input().split()))
    dic = {}
    for x in a:
        if x in dic:
            dic[x] += 1
        else:
            dic[x] = 1
    ans = 0
    for v in a:
        if dic[v] > 1:
            continue
        tmp = Divisor_Set(v)
        tmp.remove(v)
        f = True
        for x in tmp:
            if x in dic:
                f = False
                break
        if f:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from math import sqrt
from random import randint
def Divisor_Set(n):
    s = set()
    for i in range(1, int(sqrt(n))+2):
        if n%i == 0:
            s.add(i)
            s.add(n//i)
    return s

def main1():
    n = int(input())
    a = list(map(int, input().split()))
    dic = {}
    for x in a:
        if x in dic:
            dic[x] += 1
        else:
            dic[x] = 1
    ans = 0
    a.sort()
    for i in range(n):
        v = a[i]
        if dic[v] > 1:
            continue
        lim = v//2 + 1
        f = True
        for j in range(i):
            if a[j] > lim:
                break
            if a[i] % a[j] == 0:
                f = False
                break
        if f:
            ans += 1
    print(ans)

def main2():
    n = int(input())
    a = list(map(int, input().split()))
    dic = {}
    for x in a:
        if x in dic:
            dic[x] += 1
        else:
            dic[x] = 1
    ans = 0
    for v in a:
        if dic[v] > 1:
            continue
        tmp = Divisor_Set(v)
        tmp.remove(v)
        f = True
        for x in tmp:
            if x in dic:
                f = False
                break
        if f:
            ans += 1
    print(ans)

if __name__ == "__main__":
    if randint(1, 2) == 1:
        main1()
    else:
        main2()
### BUGGY CODE ###

from itertools import permutations

N, M, R = map(int, input().split())

visit = list(map(int, input().split()))
g = [[float('inf')] * N for _ in range(N)]
for i in range(N):
    g[i][i] = 0

for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    g[a][b] = c
    g[b][a] = c

for i in range(N):
    for j in range(N):
        for k in range(N):
            g[i][j] = min(g[i][j], g[i][k] + g[k][j])

cost = float('inf')

for town in permutations(visit):
    c = 0
    for i in range(R - 1):
        c += g[town[i] - 1][town[i + 1] - 1]
    cost = min(cost, c)
print(cost)


### FIXED CODE ###

from itertools import permutations

N, M, R = map(int, input().split())

visit = list(map(int, input().split()))
g = [[float('inf')] * N for _ in range(N)]
for i in range(N):
    g[i][i] = 0

for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    g[a][b] = c
    g[b][a] = c


def dijkstra(start):
    c_l = [float('inf')] * N
    c_l[start] = 0
    visited = [False] * N
    while True:
        min_v = float('inf')
        next = -1
        visited[start] = True
        for i in range(N):
            if visited[i]:
                continue
            if g[start][i]:
                d = c_l[start] + g[start][i]
                if d < c_l[i]:
                    c_l[i] = d
                if min_v > c_l[i]:
                    min_v = c_l[i]
                    next = i
        start = next
        if next == -1:
            break
    return c_l


cost_list = []
for i in range(N):
    cost_list.append(dijkstra(i))

cost = float('inf')
for town in permutations(visit):
    c = 0
    for i in range(R - 1):
        c += cost_list[town[i] - 1][town[i + 1] - 1]
    cost = min(cost, c)
print(cost)
### BUGGY CODE ###

H,W = list(map(int,input().split()))
 
A = [list(str(input())) for i in range(H)]
 
white = []
black = []
 
length = sum([a.count(".") for a in A])
cnt = 0
 
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            black.append([i,j])
        else:
            white.append([i,j])
 
while (length > 0):
    gray = []
    if len(black) > length:
       
        for l in white:
            if [l[0],l[1]-1] in black or [l[0],l[1]+1] in black or [l[0]-1,l[1]] in black or [l[0]+1,l[1]] in black:
                gray.append(l)
    
    else:       
        for l in black:
            c1 = [l[0],l[1]-1]
            if c1 in white and c1 not in gray:
                gray.append(c1)
            c2 = [l[0],l[1]+1]
            if c2 in white and c2 not in gray:
                gray.append(c2)
            c3 = [l[0]-1,l[1]]
            if c3 in white and c3 not in gray:
                gray.append(c3)
            c4 = [l[0]+1,l[1]]
            if c4 in white and c4 not in gray:
                gray.append(c4)
    
    for l in gray:
        black.append(l)
        white.remove(l)
        
    cnt += 1
    length = len(white)
    
print(cnt)

### FIXED CODE ###

H,W = list(map(int,input().split()))
A = [list(str(input())) for i in range(H)]
 
black = []
 
cnt = 0
 
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            black.append([i,j])
 
length = len(black)
            
while (length < H*W):
    gray = []
    for l in black:
        if l[1] != 0:
            c1 = (l[0],l[1]-1)
            if A[c1[0]][c1[1]] == ".":
                gray.append(c1)
                A[c1[0]][c1[1]] = "#"
        if l[1] != W-1:
            c2 = (l[0],l[1]+1)
            if  A[c2[0]][c2[1]] == ".":
                gray.append(c2)
                A[c2[0]][c2[1]] = "#"
        if l[0] != 0:
            c3 = (l[0]-1,l[1])
            if  A[c3[0]][c3[1]] == ".":
                gray.append(c3)
                A[c3[0]][c3[1]] = "#"
        if l[0] != H-1:
            c4 = (l[0]+1,l[1])
            if  A[c4[0]][c4[1]] == ".":
                gray.append(c4)
                A[c4[0]][c4[1]] = "#"
    
    gray = list(set(gray))
    black = [l for l in gray]
    
    cnt += 1
    length += len(black)
    
print(cnt)
### BUGGY CODE ###

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

for i in range(n):
    l = a[:i]+a[i+1:]
    pattern = 0
    for j in range(n):
        sum = l.count(j)
        pattern += sum*(sum-1)//2
    print(pattern)

### FIXED CODE ###

import collections

n = int(input())
a = list(map(int,input().split()))
d = collections.Counter(a)
s = sum([i*(i-1)//2 for i in d.values()])

for j in a:
    print(s-d[j]+1)
### BUGGY CODE ###

h,w,m=map(int,input().split())
lh=[0]*h
lw=[0]*w
l=[]
for i in range(m):
  h1,w1=map(int,input().split())
  l.append([h1,w1])
  lh[h1-1]+=1
  lw[w1-1]+=1

hmax=max(lh)
wmax=max(lw)
lh2=[]
lw2=[]
for i in range(h):
  if lh[i]==hmax:
    lh2.append(i)
for i in range(w):
  if lw[i]==wmax:
    lw2.append(i)

s=1
for m in lh2:
  for m2 in lw2:
    if [m+1,m2+1] not in l:
      s=0
      
print(hmax+wmax-s)

### FIXED CODE ###

h,w,m=map(int,input().split())
lh=[0]*h
lw=[0]*w
l=set()
for i in range(m):
  h1,w1=input().split()
  l.add(h1+"_"+w1)
  lh[int(h1)-1]+=1
  lw[int(w1)-1]+=1

hmax=max(lh)
wmax=max(lw)
lh2=[]
lw2=[]
for i in range(h):
  if lh[i]==hmax:
    lh2.append(i)
for i in range(w):
  if lw[i]==wmax:
    for m in lh2:
      if str(m+1)+"_"+str(i+1) not in l:
        print(hmax+wmax)
        exit()      
print(hmax+wmax-1)
### BUGGY CODE ###

MOD = 1000000007

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

f = [0] * (n + 1)
f[0] = 1

if 1 not in a:
    f[1] = 1

for i in range(2, n + 1):
    if i in a:
        continue
    f[i] = f[i - 1] + f[i - 2]
    if f[i] >= MOD:
        f[i] -= MOD

print(f[-1])


### FIXED CODE ###

def main():
    N, M, *a = map(int, open(0).read().split())
    div = 1000000007
    broken = set(a)
 
    comb_list = [0] * (N + 1)
    comb_list[0] = 1
    if 1 not in broken:
        comb_list[1] = 1
 
    for i in range(2, N + 1):
        if i in broken:
            continue
        comb_list[i] = (comb_list[i - 1] + comb_list[i - 2]) % div
 
    print(comb_list[-1])
 
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
A.insert(0,0)
X = {i:0 for i in range(-2*N,4*N+2)}
k = 0
while k<K:
    for i in range(1,N+1):
        d = A[i]
        X[2*i-2*d-1] += 1
        X[2*i+2*d+1] -= 1
    for i in range(-2*N+1,4*N+2):
        X[i] += X[i-1]
    X[0]=0
    A = [X[2*i] for i in range(N+1)]
    X = {i:0 for i in range(-2*N,4*N+2)}
    if sum(A)==N*N:
        break
    k += 1
print(*A[1:])

### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
cnt = 0
while cnt<K:
    B = [0 for _ in range(N+1)]
    for i in range(N):
        a = A[i]
        B[max(i-a,0)] += 1
        B[min(i+a,N-1)+1] -= 1
    for i in range(1,N+1):
        B[i] += B[i-1]
    A = B[:N]
    flag = 0
    for i in range(N):
        if A[i]<N:
            flag = 1
            break
    if flag==0:break
    cnt += 1
print(*A)
### BUGGY CODE ###

S = list(str(input()))
Q = int(input())
for i in range(Q):
  a = list(map(str, input().split()))
  if len(a) == 1:
    S = list(reversed(S))
  else:
    if a[1] == "1":
      S.insert(0, a[2])
    else:
      S.append(a[2])
print(''.join(S))

### FIXED CODE ###

S = list(str(input()))
Q = int(input())
s1 = []#先頭
s2 = []#後方
b = []
num_rev = 0
for i in range(Q):
  a = list(map(str, input().split()))
  if len(a) == 1:
    num_rev += 1
  else:
    if (num_rev + int(a[1]))%2==0:
      s2.append(a[2])
    else:
      s1.append(a[2])
if num_rev % 2 == 0:
  s1 = list(reversed(s1))
  s1.extend(S)
  s1.extend(s2)
  print(''.join(s1))
else:
  s2 = list(reversed(s2))
  s2.extend(list(reversed(S)))
  s2.extend(s1)
  print(''.join(s2))
### BUGGY CODE ###



# def solve(s,t,n,m,dp):
#     if n<0 or m<0:
#             return ''
#     if dp[n][m]!=-1:
#         return dp[n][m]
#     else:
#         ans=''
#         if s[n]==t[m]:
#             ans=s[n]+solve(s,t,n-1,m-1,dp)
#             dp[n][m]= ans
#         else:
#             s1=solve(s,t,n-1,m,dp)
#             s2=solve(s,t,n,m-1,dp)
#             if len(s1)>len(s2):
#                 ans=s1
#             else:
#                 ans=s2
#             dp[n][m]= ans
#         return dp[n][m]


s=input()
t=input()
dp=[[""]*(len(t)+1) for i in range(len(s)+1)]

for i in range(1,len(s)+1):
    for j in range(1,len(t)+1):
        if s[i-1]==t[j-1]:
            dp[i][j]=dp[i-1][j-1]+s[i-1]

        else:
            if len(dp[i-1][j])>len(dp[i][j-1]):
                dp[i][j]=dp[i-1][j]
            else:
                dp[i][j]=dp[i][j-1]

    # print(dp[i])


# solve(s,t,len(s)-1,len(t)-1,dp)
print(dp[-1][-1])

### FIXED CODE ###


# Returns length of LCS for X[0..m-1], Y[0..n-1] 
def lcs(X, Y, m, n): 
	L = [[0 for x in range(n+1)] for x in range(m+1)] 

	# Following steps build L[m+1][n+1] in bottom up fashion. Note 
	# that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] 
	for i in range(m+1): 
		for j in range(n+1): 
			if i == 0 or j == 0: 
				L[i][j] = 0
			elif X[i-1] == Y[j-1]: 
				L[i][j] = L[i-1][j-1] + 1
			else: 
				L[i][j] = max(L[i-1][j], L[i][j-1]) 

	# Following code is used to print LCS 
	index = L[m][n] 

	# Create a character array to store the lcs string 
	lcs = [""] * (index+1) 
	lcs[index] = "" 

	# Start from the right-most-bottom-most corner and 
	# one by one store characters in lcs[] 
	i = m 
	j = n 
	while i > 0 and j > 0: 

		# If current character in X[] and Y are same, then 
		# current character is part of LCS 
		if X[i-1] == Y[j-1]: 
			lcs[index-1] = X[i-1] 
			i-=1
			j-=1
			index-=1

		# If not same, then find the larger of two and 
		# go in the direction of larger value 
		elif L[i-1][j] > L[i][j-1]: 
			i-=1
		else: 
			j-=1

	print (''.join(lcs))

# Driver program 

s=input()
t=input()
m = len(s) 
n = len(t) 
lcs(s, t, m, n)
### BUGGY CODE ###

s = input()
dic = {}
for i in range(2019):
  dic[i] = 0
dic[0] = 1
m = 0
for j in range(1, len(s)+1):
  m = int(s[-j]) * 10**(j-1) + m
  m %= 2019
  dic[m] += 1
ans = 0
for v in dic.values():
  ans += v*(v-1) // 2
print(ans)


### FIXED CODE ###

s = input()
dic = {}
for i in range(2019):
  dic[i] = 0
dic[0] = 1
m = 0
decimal = 1
for j in range(1, len(s)+1):
  m += int(s[-j]) * decimal
  m %= 2019
  dic[m] += 1
  decimal *= 10
  decimal %= 2019

ans = 0
for v in dic.values():
  ans += v*(v-1) // 2
print(ans)
### BUGGY CODE ###

N,M=[int(x) for x in input().rstrip().split()]
A=[int(x) for x in input().rstrip().split()]
l=[]
l1=[]

for i in range(M):
    b,c=[int(x) for x in input().rstrip().split()]
    l1=[c for i in range(b)]
    l=l+l1
l.sort(reverse=True)
A=A+l[:N]
A.sort(reverse=True)
print(sum(A[:N]))

    




### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
from bisect import bisect_left
 
 
n, m = map(int, input().split())
a = list( map(int, input().split()))
a.sort()
 
bc = [tuple(map(int,input().split())) for i in range(m)]
bc = sorted(bc, reverse=True, key=lambda x: x[1])
 
i = 0
d = []
for b, c in bc:
    d.extend([c]*b)
    if len(d) >= n:
        break
 
a=a+d
a.sort(reverse=True)
print(sum(a[:n]))

#l.sort(reverse=True)
#A=A+l[:N]
#A.sort(reverse=True)
### BUGGY CODE ###

#!/usr/bin/env python3
# スペース区切りの整数の入力
n, k = map(int, input().split())
#配列の入力
data = list(map(int, input().split()))

temp = 1
old = 1
for i in range(n):
    if i < k:
        temp *= data[i]
        continue
    else:
        old = temp
        temp = temp / data[i-k] * data[i]
    #print("i:{}, k:{}".format(i, k))
    #print(score)

    if i > k-1:
        if temp > old:
            print("Yes")
        else:
            print("No")




### FIXED CODE ###

#!/usr/bin/env python3
# スペース区切りの整数の入力
n, k = map(int, input().split())
#配列の入力
data = list(map(int, input().split()))

for i in range(n-k):
    if data[i] < data[k+i]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n, k = map(int, input().split())
a = [int(i) for i in input().split()]

ans = [1] * (n-k+1)

for i in range(k):
    ans[0] *= a[i]
for i in range(1, n-k+1):
    ans[i] = (ans[i-1] / a[i-1]) * a[k+i-1]

for i in range(len(ans)-1):
    if ans[i] < ans[i+1]:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

n, k = map(int, input().split())
a = [int(i) for i in input().split()]

for i in range(n-k):
    if a[i] < a[k+i]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import sys
from bisect import bisect_left


class RangeUpdateTree:
    def __init__(self, n, initial=-1, sentinel=-2):
        n2 = 1 << n.bit_length()
        self.n = n2
        self.offset = n2
        self.data = [initial] * (n2 << 1)
        self.sentinel = sentinel

    def update(self, a, b, x):
        stack = [(1, 0, self.n)]
        while stack:
            i, l, r = stack.pop()
            if a <= l and r <= b:
                self.data[i] = x
                continue
            y = self.data[i]
            j = i << 1
            if y != self.sentinel:
                self.data[i] = self.sentinel
                self.data[j] = self.data[j + 1] = y
            m = (l + r) // 2
            if a < m:
                stack.append((j, l, m))
            if m < b:
                stack.append((j + 1, m, r))

    def aggregate(self):
        stack = [1]
        ans = 0
        while stack:
            i = stack.pop()
            if self.data[i] != self.sentinel:
                ans += self.data[i] * (self.n >> i.bit_length() - 1)
                continue
            i <<= 1
            stack.append(i)
            stack.append(i + 1)
        return ans

    def propagate(self):
        stack = [(1, 0, self.n)]
        while stack:
            i, l, r = stack.pop()
            if self.data[i] != self.sentinel:
                self.data[l + self.offset:r + self.offset] = [self.data[i]] * (r - l)
                continue
            i <<= 1
            m = (l + r) // 2
            stack.append((i, l, m))
            stack.append((i + 1, m, r))

    def debug_print(self):
        i = 1
        while i <= self.offset:
            print(self.data[i:2 * i])
            i <<= 1


n, q = list(map(int, input().split()))
lines = sys.stdin.readlines()
kkk = []
for line in lines[:n]:
    s, t, x = list(map(int, line.split()))
    kkk.append((x, s, t))
kkk.sort(reverse=True)
ddd = list(map(int, lines[n:]))
max_d = ddd[-1]
rut = RangeUpdateTree(q)
for x, s, t in kkk:
    sx = s - x
    tx = t - x
    if tx <= 0 or sx > max_d:
        continue
    ss = bisect_left(ddd, sx)
    tt = bisect_left(ddd, tx)
    if ss == tt:
        continue
    # print(x, s, t, s - x, t - x, ss, tt)
    rut.update(ss, tt, x)
rut.propagate()
data = rut.data[rut.offset:]
# rut.debug_print()
print('\n'.join(map(str, data[:q])))


### FIXED CODE ###

import sys
from bisect import bisect_left

n, q = map(int, input().split())
lines = sys.stdin.readlines()
kkk = []
for line in lines[:n]:
    s, t, x = map(int, line.split())
    kkk.append((x, s, t))
kkk.sort()
ddd = list(map(int, lines[n:]))

ans = [-1] * q
skip = [-1] * q
for x, s, t in kkk:
    ss = bisect_left(ddd, s - x)
    tt = bisect_left(ddd, t - x)
    while ss < tt:
        if skip[ss] == -1:
            ans[ss] = x
            skip[ss] = tt
            ss += 1
        else:
            ss = skip[ss]
print('\n'.join(map(str, ans)))
### BUGGY CODE ###

from bisect import bisect_left,bisect_right
N=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]

a=len(bin(max(A)))
b=len(bin(max(B)))

num=[0]*30
for i in range(max(a,b)):
    t = pow(2,i)
    K=[i%(2*t) for i in A]
    L=[i%(2*t) for i in B]
    L.sort()
    #print(K,L)
    a = 0
    for k in K:
        x = bisect_left(L,2*t-k)-bisect_left(L,t-k)
        y = bisect_left(L,4*t-k)-bisect_left(L,3*t-k)
        #print(x,y)
        a =(a+x+y)%2
    num[i]=a
ans =0
s=1
for z in num:
    ans += z*s
    s*=2
print(ans)

### FIXED CODE ###

from bisect import bisect_left,bisect_right
N=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]

num=[0]*30
for i in range(30):
    t = pow(2,i)
    K=sorted(i%(2*t) for i in A)
    L=sorted(i%(2*t) for i in B)
    #L=sort()
    #print(K,L)
    a = 0
    #尺取り法,i*tより小さい整数を数える
    S=[i*t for i in range(1,5)]
    count=[N]*4
    for k in K:
        for j in range(4):
            while L[count[j]-1]+k>=S[j] and count[j]>0:
                count[j]-=1
        a +=count[3]-count[2]+count[1]-count[0]
        #print(count,a)
    num[i]=a%2
ans =0
s=1
for z in num:
    ans += z*s
    s*=2
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))

def center(x):
    return sum(list(range(x+1)))/x

P = [center(p) for p in P]

print(max([sum(P[i:i+K]) for i in range(N-K+1)]))

### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))

P = [(1+p)/2 for p in P]

S = [P[0]]
for i in range(1,N):
    S.append(P[i]+S[i-1])

S.insert(0,0)

b = max([S[i]-S[i-K] for i in range(K, N+1)])

print(b)
### BUGGY CODE ###

import heapq
def dijkstra_heap():
    used = [-1] * (2501*n)
    edgelist=[]
    d=[0]*n
    d[0]=1
    f=1
    for i in range(0,2501):
        if 0<=ss+i*cd[0][0]<=2500:
            heapq.heappush(edgelist,[cd[0][1]*i,cd[0][0]*i+ss])
        else:
            break
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if used[minedge[1]]!=-1:
            continue
        v = minedge[1]
        kai=minedge[0]
        mai=v%2501
        used[v] = kai
        if d[v//2501]==0:
            d[v//2501]=1
            f+=1
            if f==n:
                return used
        for e in edge[v//2501]:
            if mai-e[1]>=0:
                for i in range(2501):
                    sss=mai-e[1]+cd[e[2]][0]*i
                    if 0<=sss<=2500:
                        if used[e[2]*2501+sss]==-1:
                            heapq.heappush(edgelist,[e[0]+kai+cd[e[2]][1]*i,e[2]*2501+sss])  
                    else:
                        break
    return used

################################
n,m,ss = map(int,input().split())
ss=min(2500,ss)
edge = [[] for i in range(n)]

for i in range(m):
    x,y,a,b = map(int,input().split())
    edge[x-1].append([b,a,y-1])
    edge[y-1].append([b,a,x-1])
cd=[]
for i in range(n):
    cd.append(list(map(int,input().split())))
pp=dijkstra_heap()
for i in range(1,n):
    ans=10**20
    for j in range(2501):
        if pp[i*2501+j]!=-1:
            ans=min(ans,pp[i*2501+j])
    print(ans)

### FIXED CODE ###

import heapq
def dijkstra_heap():
    used = [-1] * (2451*n)
    edgelist=[]
    heapq.heappush(edgelist,[0,ss])
    while len(edgelist):
        #print(len(edgelist))
        minedge = heapq.heappop(edgelist)
        if used[minedge[1]]!=-1:
            continue
        v = minedge[1]
        kai=minedge[0]
        mai=v%2451
        used[v] = kai
        for e in edge[v//2451]:
            if mai-e[1]>=0:
                sss=mai-e[1]
                if used[e[2]*2451+sss]==-1:
                    heapq.heappush(edgelist,[e[0]+kai,e[2]*2451+sss])
        if mai+cd[v//2451][0]<=2450:
            if used[v+cd[v//2451][0]]==-1:
                heapq.heappush(edgelist,[kai+cd[v//2451][1],v+cd[v//2451][0]])
    return used

################################
n,m,ss = map(int,input().split())
ss=min(2450,ss)
edge = [[] for i in range(n)]

for i in range(m):
    x,y,a,b = map(int,input().split())
    edge[x-1].append([b,a,y-1])
    edge[y-1].append([b,a,x-1])
cd=[]
for i in range(n):
    cd.append(list(map(int,input().split())))
pp=dijkstra_heap()
for i in range(1,n):
    ans=10**20
    for j in range(2451):
        if pp[i*2451+j]!=-1:
            ans=min(ans,pp[i*2451+j])
    print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,q=map(int,input().split())
s=str(input())
l=[0]*q
r=[0]*q
for i in range(q):
        l[i],r[i]=map(int,input().split())

t=s.replace('A'+'C','*_')
a=[0]
for i in range(n):
        if t[i]=='*':
                a.append(i+1)
a.append(len(s))
for i in range(q):
        count=0
        for j in range(len(a)):
                if l[i]<=a[j]<=r[i]-1:
                        count+=1
                elif a[j]<l[i]:
                        continue
                else:
                        break
        print(count)




### FIXED CODE ###

import sys
input = sys.stdin.readline
n,q=map(int,input().split())
s=str(input())

t=[0]*n
for i in range(n-1):
        t[i+1]=t[i]+(1 if s[i:i+2]=='AC' else 0)
for j in range(q):
        l,r=map(int,input().split())
        print(t[r-1]-t[l-1])
### BUGGY CODE ###

n = int(input())
s = input()

cnt = 0
for i in range(n):
    for j in range(i+1, n):
        if s[i] != s[j]:
            for k in range(j+1, n):
                if j-i != k-j:
                    if s[k]!=s[i] and s[k]!=s[j]:
                        cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
s = input()

R = [0]*n # R[i] := i文字目より右にある'R'の個数
G = [0]*n
B = [0]*n

# R
for i in range(n-2, -1, -1):
    if s[i+1] == 'R':
        R[i] = R[i+1] + 1
    else:
        R[i] = R[i+1]
# G
for i in range(n-2, -1, -1):
    if s[i+1] == 'G':
        G[i] = G[i+1] + 1
    else:
        G[i] = G[i+1]
# B
for i in range(n-2, -1, -1):
    if s[i+1] == 'B':
        B[i] = B[i+1] + 1
    else:
        B[i] = B[i+1]

cnt = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        if s[i] != s[j]:
            Set = set((s[i], s[j]))
            if Set == set(('R', 'G')):
                cnt += B[j]
                if j+(j-i) < n:
                    if s[j+(j-i)] == 'B':
                        cnt -= 1
            elif Set == set(('G', 'B')):
                cnt += R[j]
                if j+(j-i) < n:
                    if s[j+(j-i)] == 'R':
                        cnt -= 1
            else:
                cnt += G[j]
                if j+(j-i) < n:
                    if s[j+(j-i)] == 'G':
                        cnt -= 1
print(cnt)