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

param_a = int(input())

for i in range(1000000):
    param_str = '7'*(i+1)
    param_int = int(param_str)
    
    if param_int % param_a == 0:
        param_answer = i+1
        break

try:
    print(param_answer)
except:
    print(-1)

### FIXED CODE ###

# https://atcoder.jp/contests/abc174/submissions/15768313 さんの回答、参照

K = int(input())
num = 0
if K%2 == 0:
    print(-1)
else:
    for i in range(1, 1000000):
        num = num*10 + 7
        num %= K
        if num == 0:
            print(i)
            break
    else:
        print(-1)
### BUGGY CODE ###

import collections
n = int(input())
s = []
for i in range(n):
    s.append(input())
    
dic = collections.Counter(s)
    
ans = sorted([k for k, v in dic.items() if v == max(dic.values())])

for i in range(len(ans)):
    print(ans[i])

### FIXED CODE ###

import collections
n = int(input())
s = []
for i in range(n):
    s.append(input())
    
dic = collections.Counter(s)
dic = dic.most_common()

ans = [dic[0][0]]

for i in range(len(dic)-1):
    if dic[i][1] == dic[i+1][1]:
        ans.append(dic[i+1][0])
    else:
        break
        
ans = sorted(ans)

for i in range(len(ans)):
    print(ans[i])
### BUGGY CODE ###

N,K = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
l = []
for a,b in AB:
  ab = [a]*b
  l.extend(ab)

l.sort()
print(l[K-1])

### FIXED CODE ###

N,K = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
count = 0
AB.sort()
for a,b in AB:
  count += b
  if count >= K:
    print(a)
    exit()
### BUGGY CODE ###

from queue import deque
H, W = map(int, input().split())

matrix = []

visited = set()

for i in range(H):
    matrix.append(list(input()))

que = deque([])

for i in range(H):
    for j in range(W):
        if matrix[i][j] == '#' and (i, j) not in visited:
            visited.add((i, j))
            for ud, lr in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                if not(0 <= i+ud < H and 0 <= j+lr < W)  or matrix[i+ud][j+lr] == '#':
                    continue
                que.append((i+ud, j+lr))

res = 0

while que:
    for k in range(len(que)):
        i, j = que.popleft()
        if (i, j) in visited:
            continue
        visited.add((i, j))
        for ud, lr in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            if not(0 <= i+ud < H and 0 <= j+lr < W)  or matrix[i+ud][j+lr] == '#':
                continue
            que.append((i+ud, j+lr))
    if que:
        res += 1
print(res)



### FIXED CODE ###

H, W = map(int, input().split())

matrix = []

visited = set()

for i in range(H):
    matrix.append(list(input()))

visited = set()

for i in range(H):
    for j in range(W):
        if matrix[i][j] == '#' and (i, j) not in visited:
            for ud, lr in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                if not(0 <= i+ud < H and 0 <= j+lr < W)  or matrix[i+ud][j+lr] == '#':
                    continue
                visited.add((i+ud, j+lr))
                matrix[i+ud][j+lr] = '#'

res = 0

while visited:
    res += 1
    buf = set()
    for i, j in visited:
        if matrix[i][j] == '#' and (i, j) not in buf:
            for ud, lr in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                if not(0 <= i+ud < H and 0 <= j+lr < W)  or matrix[i+ud][j+lr] == '#':
                    continue
                buf.add((i+ud, j+lr))
                matrix[i+ud][j+lr] = '#'
    if not buf:
        break
    visited = buf

print(res)
### BUGGY CODE ###

n, k = map(int, input().split())
A = list(map(int, input().split()))
route = [1]
dest = A[0]
while dest not in route:
    route.append(dest)
    dest = A[dest - 1]
ind = route.index(dest)
cycle = route[ind:]
if k >= ind:
    ans = (k - ind) % len(cycle)
    print(cycle[ans])
else:
    print(route[k])

### FIXED CODE ###

n, k = map(int, input().split())
A = list(map(int, input().split()))
route = [1]
dest = A[0]
check = {i: False for i in range(n)}
while not check[dest - 1]:
    check[dest - 1] = True
    route.append(dest)
    dest = A[dest - 1]
ind = route.index(dest)
cycle = route[ind:]
if k >= ind:
    ans = (k - ind) % len(cycle)
    print(cycle[ans])
else:
    print(route[k])
### BUGGY CODE ###

import sys

x =lambda:list(map(int,sys.stdin.readline().strip().split()))
n,m=x()
adjac = {i:[] for i in range(1,n+1)}

for _ in range(m):
    a,b = x()
    adjac[a].append(b)
    adjac[b].append(a)

comp = []

visited = {i:False for i in range(1,n+1)}

for i in range(1,n+1):

    if not visited[i]:
        queue = [i]
        count=1
        visited[i] = True
        while len(queue)!=0:
            h=queue[0]
            queue.pop(0)
            arr = adjac[h]
            # print(arr,i)
            for j in arr:
                if not visited[j]:
                    # print(j,h)
                    visited[j]=True
                    queue.append(j)
                    count+=1
        comp.append(count)
print(max(comp))

### FIXED CODE ###

import sys

x =lambda:list(map(int,sys.stdin.readline().strip().split()))
n,m=x()
adjac = {i:[] for i in range(1,n+1)}

for _ in range(m):
    a,b = x()
    adjac[a].append(b)
    adjac[b].append(a)

comp = 0

visited = {i:False for i in range(1,n+1)}

for i in range(1,n+1):

    if not visited[i]:
        queue = [i]
        count=1
        visited[i] = True
        while len(queue)!=0:
            h=queue[0]
            queue.pop(0)
            arr = adjac[h]
            # print(arr,i)
            for j in arr:
                if not visited[j]:
                    # print(j,h)
                    visited[j]=True
                    queue.append(j)
                    count+=1
        comp=max(comp,count)
print(comp)
### BUGGY CODE ###

# coding: utf-8

n, k = map(int, input().rstrip().split())    # 2 <= n <= 10^5, 1 <= k <= 100
h = list(map(int, input().rstrip().split()))

dp = [float('inf')] * 100010
dp[0] = 0
for i in range(1, n):
    for j in range(max(i - k, 0), i):
        dp[i] = min(dp[i], dp[j] + abs(h[i] - h[j]))
print(dp[i])


### FIXED CODE ###

# coding: utf-8

def f(n, k, h):
    dp = [0 for _ in range(n)]
    for i in range(1, n):
        js = max(i - k, 0)
        dp[i] = min(dp[j] + abs(h[i] - h[j]) \
            for j in range(js, i))
        # print(dp)
    return(dp[i])

n, k = map(int, input().rstrip().split())    # 2 <= n <= 10^5, 1 <= k <= 100
h = list(map(int, input().rstrip().split()))

print(f(n, k, h))
### BUGGY CODE ###

import random
from collections import defaultdict
from itertools import accumulate
n = int(input())
s = input()
mod = (1<<61)-1
base = 1000+random.randint(0,100)
power = [1]
for i in range(1,n):
	power.append((power[-1]*base)&mod)
hvalue = [0]
for i in range(n):
	hvalue.append((hvalue[-1]+(ord(s[i])*power[i]))&mod)
def rollinghash(l,r):
	return ((hvalue[r]-hvalue[l])*power[n-r])&mod
ans = 0
for i in range(1,n//2+1):
	dc = defaultdict(tuple)
	for j in range(n-i+1):
		x = rollinghash(j,i+j)
		if dc[x]:
			lf,rg = dc[x]
			if rg<=j:
				ans = max(ans,i)
		else:
			dc[x] = (j,i+j)
print(ans)

### FIXED CODE ###

import random
from collections import defaultdict
from itertools import accumulate
import sys
input = sys.stdin.readline
n = int(input())
s = input().rstrip()
mod = (1<<61)-1
base = 1000+random.randint(0,100)
power = [1]
for i in range(1,n):
  power.append((power[-1]*base)%mod)
hvalue = [0]
for i in range(n):
  hvalue.append((hvalue[-1]+(ord(s[i])*power[i]))%mod)
def rollinghash(l,r):
  return ((hvalue[r]-hvalue[l])*power[n-r])%mod
def pun(i):
  dc = defaultdict(int)
  if i>n//2:
    return False
  for j in range(n-i+1):
    x = rollinghash(j,i+j)
    if dc[x]:
      rg =dc[x]
      if rg<=j:
        return True
    else:
      dc[x] = i+j
  return False
l=0
r=n//2+1
while l+1<r:
  mi=(l+r)//2
  if pun(mi):
    l=mi
  else:
    r=mi
print(l)
### BUGGY CODE ###

def main():
  import sys
  num,capacity=map(int,input().split())
  items=tuple([list(map(int,sys.stdin.readline().split())) for _ in range(num)])
  DP=[-1]*(capacity+1)
  DP[0]=0
  for item in items:
    weight=item[0]
    value=item[1]
    left=capacity-weight
    for i in range(left,-1,-1):
      if DP[i]<0:
        continue
      DP[i+weight]=max(DP[i]+value,DP[i+weight])
  print(max(DP))
      
if __name__=="__main__":
  main()

### FIXED CODE ###

n,w=map(int,input().split())
goods=[list(map(int,input().split())) for _ in range(n)]
DP=[[0]*(w+1) for _ in range(n+1)]
for i in list(range(n))[::-1]:
  wi,vi=goods[i][0],goods[i][1]
  for j in range(w+1):
    if j<wi:
      DP[i][j]=DP[i+1][j]
    else:
      DP[i][j]=max(DP[i+1][j],DP[i+1][j-wi]+vi)
print(DP[0][w])
### BUGGY CODE ###

n = int(input())
factor = []

for i in range(1,int(n**1/2)+1):
    if n%i == 0:
        factor.append(i + n//i -2)

factor.sort()
print(factor[0])

### FIXED CODE ###

n = int(input())
factor = []

for i in range(1,int(n**0.5)+1):
    if n%i == 0:
        factor.append(i + n//i)

factor.sort()
print(factor[0]-2)
### BUGGY CODE ###

n= int(input())
a = list(map(int, input().split()))
q = int(input())
b = [list(map(int,input().split())) for i in range(q)]
num = [0]*(10**5+1)
for i in a:
  num[i] = a.count(i)
sum_a = sum(a)

for i in range(q):
  dif = b[i][1]-b[i][0]
  #print(dif)
  sum_a += dif*num[b[i][0]]
  num[b[i][1]] += num[b[i][0]]
  num[b[i][0]] = 0
  print(sum_a)

### FIXED CODE ###

n= int(input())
a = list(map(int, input().split()))
q = int(input())
b = [list(map(int,input().split())) for i in range(q)]
num = [0]*(10**5+1)
for i in a:
  num[i] += 1
sum_a = sum(a)

for i in range(q):
  dif = b[i][1]-b[i][0]
  #print(dif)
  sum_a += dif*num[b[i][0]]
  num[b[i][1]] += num[b[i][0]]
  num[b[i][0]] = 0
  print(sum_a)
### BUGGY CODE ###

N = int(input())
result = []
for i in range(N):
    s = str(input())
    if s not in result:
        result.append(s)
print(len(result))

### FIXED CODE ###

N = int(input())
s = [str(input()) for i in range(N)]
s = set(s)
print(len(s))
### BUGGY CODE ###

def main():
  s=input()
  q=int(input())
  for _ in [0]*q:
    a=list(input().split())
    if len(a)==1:
      s=s[::-1]
    else:
      if a[1]=='1':
        s=a[2]+s
      else:
        s=s+a[2]
  print(s)
if __name__=='__main__':
  main()

### FIXED CODE ###

def main():
  from collections import deque
  s=deque(input())
  q=int(input())
  count=0
  for _ in [0]*q:
    a=list(input().split())
    if len(a)==1:
      count+=1
    else:
      if count%2==0:
        if a[1]=='1':
           s.appendleft(a[2])
        else:
          s.append(a[2])
      else:
        if a[1]=='1':
          s.append(a[2])
        else:
          l=(a[2],s)
          s.appendleft(a[2])
  if count%2==1:
    s=list(s)[::-1]
  print(''.join(s))
if __name__=='__main__':
  main()
### BUGGY CODE ###


M = 998244353

n = int(input())
xs = [0] * n
ds = [0] * n
for i in range(n):
    x, d = (int(c) for c in input().split())
    ds[i] = d
    xs[i] = (x,i)

import sys
sys.setrecursionlimit(max(1000,n))

xs.sort()
index = [x[1] for x in xs]
xs = [x[0] for x in xs]
ds = [ds[ind] for ind in index]

def _sub(i):
    # 深さ優先探索しながらi番目以下の組み合わせと、次に調べるべき番号を返す
    if i==n-1:
        return 2, n
    res = 1
    ind = i+1
    while True:
        if (xs[i]+ds[i] <= xs[ind]):
            break
        o, ind = _sub(ind)
        res *= o
        res %= M
        if ind>=n:
            break
    return res+1, ind
out = []
done = 0
while True:
    o, done = _sub(done)
    out.append(o)
    if done>=n:
        break
result = 1
for o in out:
    result *= o
    result %= M
print(result)

### FIXED CODE ###


import numpy as np

M = 998244353

n = int(input())
xs = [0] * n
ds = [0] * n
for i in range(n):
    x, d = (int(c) for c in input().split())
    ds[i] = d
    xs[i] = x
xs = np.array(xs)
ds = np.array(ds)

import sys
sys.setrecursionlimit(max(1000,n))

index = xs.argsort()
xs = xs[index]
ds = ds[index]

def _sub(i):
    # 深さ優先探索しながらi番目以下の組み合わせと、次に調べるべき番号を返す
    if i==n-1:
        return 2, n
    res = 1
    ind = i+1
    while True:
        if (xs[i]+ds[i] <= xs[ind]):
            break
        o, ind = _sub(ind)
        res *= o
        res %= M
        if ind>=n:
            break
    return res+1, ind
out = []
done = 0
while True:
    o, done = _sub(done)
    out.append(o)
    if done>=n:
        break
result = 1
for o in out:
    result *= o
    result %= M
print(result)
### BUGGY CODE ###

import sys
from math import sqrt
from collections import Counter, defaultdict, deque

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)


def I():
    return int(input())


def MI():
    return map(int, input().split())


def LI():
    return list(MI())


def LIN(n: int):
    return [I() for _ in range(n)]


inf = float("inf")
mod = 10 ** 9 + 7


def main():
    s = input().rstrip()

    li = {}
    for i in range(6, 1000):
        n = str(19 * i)[-3:]
        if not ("0" in n):
            li[i] = n

    lens = len(s)
    c = 0
    for k, v in li.items():
        for pos in range(lens):
            if s[: pos + 1].endswith(v):
                if s[: pos + 1].endswith(str(2019 * k)):
                    c += 1

    print(c)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import numpy as np

input = sys.stdin.readline


def ST():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return map(int, input().split())


def LI():
    return list(MI())


S = ST()

cnt = np.zeros(2019)
cnt[0] = 1
res = 0
tmp = 1
for s in S[::-1]:
    res += int(s) * tmp
    res %= 2019
    cnt[res] += 1
    tmp *= 10
    tmp %= 2019

ans = 0
for c in cnt[cnt >= 2]:
    ans += c * (c - 1) // 2

print(int(ans))
### BUGGY CODE ###

import heapq
X, Y, Z, K = map(int, raw_input().split())
A = map(int, raw_input().split())
B = map(int, raw_input().split())
C = map(int, raw_input().split())

h1 = []
for a in A:
  for b in B:
    heapq.heappush(h1, -a - b)


h2 = []
for _ in range(X * Y):
  ab = -heapq.heappop(h1)
  for c in C:
    heapq.heappush(h2, -ab - c)

for _ in range(K):
  print -heapq.heappop(h2)

### FIXED CODE ###

import heapq
X, Y, Z, K = map(int, raw_input().split())
A = map(int, raw_input().split())
B = map(int, raw_input().split())
C = map(int, raw_input().split())

h1 = []
for a in A:
  for b in B:
    heapq.heappush(h1, -a - b)

h2 = []
for _ in range(min(K, X * Y)):
  ab = -heapq.heappop(h1)
  for c in C:
    heapq.heappush(h2, -ab - c)

for _ in range(K):
  print -heapq.heappop(h2)
### BUGGY CODE ###

import sys
from heapq import heappush, heappop

N=input()
nl=[ [ float("inf") for j in range(N+1) ] for i in range(N+1) ] 

hq=[]
for i in range(N):
	L=map(int, sys.stdin.readline().split())
	for j in range(i+1,N):
		heappush( hq, (L[j],i+1,j+1) )


ans=0
for n in range(N-1):
	cost,x,y,=heappop( hq )
	nl[x][y]=cost
	nl[y][x]=cost
	ans+=cost

def dij(start,end):
	d=[ float("inf") for _ in range(N+1)]
	d[start]=0
	q=[]
	heappush( q, start )	#u: chouten

	while q:
		fro=heappop(q)
		for to in range(1,N+1):
			alt=d[fro]+nl[fro][to]
			if d[to]>alt:
				d[to]=alt
				heappush(q,to)
	return d[end]


while hq:
	cost,x,y,=heappop( hq )
	d=dij(x,y)

	if d<cost:
		print -1
		quit()
	elif cost<d:
		ans+=cost
	nl[x][y]=cost
	nl[y][x]=cost


print ans


### FIXED CODE ###

import numpy as np
N = input()
A = [np.array(map(int,raw_input().split()), dtype=np.int64) for _ in [0]*N]
inf = 10**10
for i in range(N):
    A[i][i] = inf
#print A


result = 0
for i in range(N-1):
    for j, d1 in enumerate(A[i][i+1:], start=i+1):
	#print i,j,A[i], A[j], np.min(A[i]+A[j]),d1
        d2 = np.min(A[i]+A[j])
        if d1 >= d2:
            if d1 > d2:
                print(-1)
                exit()
        else:
            result += d1
print(result)
### BUGGY CODE ###

H, W = map(int, input().split())
S = [input() for _ in range(H)]


def f(h, w):
    c = 0
    for hh in range(h, -1, -1):
        if S[hh][w] == '#':
            break
        c += 1
    for hh in range(h, H):
        if S[hh][w] == '#':
            break
        c += 1
    for ww in range(w, -1, -1):
        if S[h][ww] == '#':
            break
        c += 1
    for ww in range(w, W):
        if S[h][ww] == '#':
            break
        c += 1
    return c - 3


def main():
    ans = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '#':
                continue
            ans = max(ans, f(h, w))
    print(ans)


main()


### FIXED CODE ###

H, W = map(int, input().split())
S = [input() for _ in range(H)]


def main():
    cnt = [[0] * W for _ in range(H)]
    for h in range(H):
        done = [0] * W
        for w in range(W):
            if S[h][w] == '#' or done[w] == 1:
                continue
            c = 0
            while W > w + c:
                if S[h][w + c] == '#':
                    break
                c += 1
            for k in range(c):
                cnt[h][w + k] += c
                done[w + k] = 1
    for w in range(W):
        done = [0] * H
        for h in range(H):
            if S[h][w] == '#' or done[h] == 1:
                continue
            c = 0
            while H > h + c:
                if S[h + c][w] == '#':
                    break
                c += 1
            for k in range(c):
                cnt[h + k][w] += c
                done[h + k] = 1
    ans = 0
    for r in cnt:
        for c in r:
            ans = max(ans, c - 1)
    print(ans)


main()
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=''
for i in range(1,n+1):
    ans+=str(a.index(i)+1)+' '
print(ans)

### FIXED CODE ###

n=int(input())
a=input().split()
ans=['' for _ in range(n)]
for i in range(n):
    s=int(a[i])
    ans[s-1]=str(i+1)
print(' '.join(ans))
### BUGGY CODE ###

from collections import deque

x,y,a,b,c=map(int, input().split())
pi=list(map(int,input().split()))
qi=list(map(int,input().split()))
ri=list(map(int,input().split()))
pi.sort(reverse=True)
qi.sort(reverse=True)
ri.sort(reverse=True)
ri=deque(ri)

apple=pi[:x]+qi[:y]
apple.sort(reverse=True)
apple=deque(apple)
while min(apple) <= ri[0]:
    c=ri.popleft()
    apple[-1]=c
    if len(ri)==0:
        break
print(sum(apple))

### FIXED CODE ###

from collections import deque
x,y,a,b,c=map(int, input().split())
pi=list(map(int,input().split()))
qi=list(map(int,input().split()))
ri=list(map(int,input().split()))
pi.sort(reverse=True)
qi.sort(reverse=True)

apple=pi[:x]+qi[:y]+ri
apple.sort(reverse=True)

print(sum(apple[:x+y]))
### BUGGY CODE ###

#EDP-E
import sys
n,W = map(int, sys.stdin.readline().split())

dp = [[ float('inf') for i in range(100001)] for _ in range(n)]


w, v = map(int, sys.stdin.readline().split())
dp[0][v] = w

for i in range(1, n):
    w, v = map(int, sys.stdin.readline().split())
    for vb in range(100001):
        if dp[i-1][vb] != float('inf'):
            dp[i][vb] = dp[i-1][vb]
            tmp = min(dp[i][vb + v], dp[i-1][vb] + w)
            if tmp <=W:
                dp[i][vb + v] = tmp
                #print(vb + v, dp[i][vb+ v])
    dp[i][v] = min(dp[i][v], w)

ans =0
for v, w in enumerate(dp[n-1]):
    if w <=W and ans <=v:
        ans = v
print(ans)

### FIXED CODE ###

import sys
n, limit = map(int, sys.stdin.readline().split()) 
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

dp = [dict() for i in range(n)]
#print(dp)
dp[0][L[0][1]] = L[0][0]

for i in range(1, n):
    dp[i][L[i][1]] = min(L[i][0], dp[i-1].get(L[i][1], float('inf')))
    for v, w in dp[i-1].items():
        dp[i][v] = min(dp[i-1][v], dp[i].get(v, float('inf')))
        dp[i][L[i][1] + v] = min(L[i][0] + dp[i-1][v], dp[i-1].get(L[i][1] + v, float('inf'))) 
        
ans = 0
for v, w in dp[-1].items():
    if w <=limit:
        if ans < v:
            ans = v
#print(dp)
print(ans)
### BUGGY CODE ###

N = input()
takahashi_v = []
aoki_v = []
for _ in range(N):
    a, b  = map(int, raw_input().split())
    record = [a, b, True]
    takahashi_v.append(record)
    aoki_v.append(record)
takahashi_v.sort(key=lambda x: (x[0] + x[1], x[0], -x[1]), reverse=True)
aoki_v.sort(key=lambda x: (x[0] + x[1], x[1], -x[0]), reverse=True)

res = 0
for _ in range(N):
    j = 0
    while j < N:
        if takahashi_v[j][2]:
            res += takahashi_v[j][0]
            takahashi_v[j][2] = False
            break
        j += 1
    if j >= N:
        break

    k = 0
    while k < N:
        if aoki_v[k][2]:
            res -= aoki_v[k][1]
            aoki_v[k][2] = False
            break
        k += 1
    if k >= N:
        break
print res

### FIXED CODE ###

N = input()
val= []
for _ in xrange(N):
    a, b  = map(int, raw_input().split())
    val.append((a + b, a, b))
val.sort(reverse=True)

res = 0
for i, (v, a, b) in enumerate(val):
    res += a if i % 2 == 0 else -b
print res
### BUGGY CODE ###

n=int(input())
s=list(input())
from collections import Counter
myc= Counter(s)
val=list(myc.values())
if len(val)!=3:
    print(0)
else:
    ans=val[0]*val[1]*val[2]
    for i in range(n-2):
        for j in range(i+1,n-1):
            if 2*j-i < n:
                if len(set(list((s[i],s[j],s[2*j-i]))))==3:
                    ans-=1
    print(ans)

### FIXED CODE ###

n=int(input())
s=list(input())
from collections import Counter
myc= Counter(s)
val=list(myc.values())
if len(val)!=3:
    print(0)
else:
    ans=val[0]*val[1]*val[2]
    for i in range(n-2):
        for j in range(i+1,n-1):
            if 2*j-i < n:
                if len(set(list((s[i],s[j],s[2*j-i]))))==3:
                    ans-=1
    print(ans)
### BUGGY CODE ###

def main():
    N = int(input())
    S = input()
    # N = 39
    # S = 'RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB'
    
    # R, G, B = [], [], []
    # for i, s in enumerate(S):
    #     if s == 'R':
    #         R.append(i)
    #     elif s == 'G':
    #         G.append(i)
    #     elif s == 'B':
    #         B.append(i)
    C = 0
    out = 0
    # for i in R:
    # for i in B:
    for i in range(len(S)):
        
        
        # for j in G:
        # for j in B:
        for j in range(len(S)):
            
            if i >= j:
                continue
            

            # for k in B:
            # for k in G:
            # for k in R:
            for k in range(len(S)):
                
                if j >= k:
                    continue
                
                # if (1 <= i < j < k < N) and (j - i != k - j):
                #     C += 1
             
                if not (j - i) == (k - j):
                    if (S[i] != S[j]) and (S[i] != S[k]) and (S[k] != S[j]):
                    
                    # if (S[i] != S[j]) and (S[i] != S[k]) and (S[j] != S[k]):
                    #     C += 1
                        # print('1:', i, j, k)
                        
                        
                        out += 1

                # if (j - i) == (k - j):
                #     print('---------------------------')
                #     print('2:', i, j, k)
                #     print('j - i, k - j:', j - i, k - j)
    
    # print(C, out)
    # print(R)
    # print(G)
    # print(B)
    # print(len(R) * len(G) * len(B))
    print(out)

    
main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(300000)
from collections import defaultdict
 
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')
 
 
N = I()
S = input()

# N = 39
# S = 'RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB'
 
d = defaultdict(int)
for c in S:
    d[c] += 1
plus = d['R'] * d['G'] * d['B']

# print(plus)
 
minus = 0
for j in range(1, N - 1):
    for l in range(1, N):
        i, k = j - l, j + l
        if i < 0 or k > N - 1:
            break
        if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
            minus += 1
 
print(plus - minus)