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

from collections import deque

H,W,K=map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())
start = (x1-1,y1-1);goal = (x2-1,y2-1)
S=[list(input()) for _ in range(H)]

def bfs(s):
  seen = [[0 for i in range(W)] for j in range(H)]
  d = [[0 for i in range(W)] for j in range(H)]
  todo = deque()
  now = s
  if S[now[0]][now[1]]=='@':return 0
  seen[now[0]][now[1]] = 1
  todo.append(now)
  while todo:
    now = todo.popleft()
    dx,dy = (1,-1,0,0),(0,0,1,-1)
    for i in range(4):
      for k in range(K):
        new = (now[0]+dx[i]*(k+1), now[1]+dy[i]*(k+1))
        if new[0]<0 or new[0]>=H:break
        if new[1]<0 or new[1]>=W:break
        if seen[new[0]][new[1]]==1:continue
        if S[new[0]][new[1]]=='@':break
        seen[new[0]][new[1]] = 1
        todo.append(new)
        d[new[0]][new[1]] = d[now[0]][now[1]] + 1
  return d

d = bfs(start)
print(d[goal[0]][goal[1]] if d[goal[0]][goal[1]] > 0 else -1)

### FIXED CODE ###

from collections import deque

def main():
  H,W,K=map(int,input().split())
  x1,y1,x2,y2 = map(lambda x: int(x)-1,input().split())
  S=[list(input()) for _ in range(H)]
  INF = 10**20

  def bfs(x0,y0,x_goal,y_goal):
    seen = [[0 for i in range(W)] for j in range(H)]
    d = [[INF for i in range(W)] for j in range(H)]
    d[x0][y0] = 0
    todo = deque()
    seen[x0][y0] = 1
    todo.append((x0,y0))
    while todo:
      x0,y0 = todo.popleft()
      dx,dy = (1,-1,0,0),(0,0,1,-1)
      for i in range(4):
        for k in range(K):
          x,y = x0+dx[i]*(k+1), y0+dy[i]*(k+1)
          if x<0 or x>=H:break
          if y<0 or y>=W:break
          if d[x][y] < d[x0][y0] + 1: break
          if S[x][y]=='@':break
          if seen[x][y]: continue
          seen[x][y] = 1
          todo.append((x,y))
          d[x][y] = d[x0][y0] + 1
          if x==x_goal and y == y_goal: return d[x][y]
    return d[x_goal][y_goal]

  ans = bfs(x1,y1,x2,y2)
  print(ans if ans < INF else -1)
  
if __name__ == "__main__":
  main()
### BUGGY CODE ###

import sys
import fractions
import math
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
a = IL()

tmp = 1
for i in a:
  if tmp%i == 0:
    continue
  tmp = i*tmp//fractions.gcd(i, tmp)

ans = 0
for i in a:
  ans += tmp//i
#print(tmp)
print(ans %mod)

### FIXED CODE ###

import sys
import fractions
import math
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
a = IL()

tmp = 1
for i in a:
  tmp = (i//fractions.gcd(i, tmp)) * tmp

ans = 0
for i in a:
  ans += tmp//i
#print(tmp)
print(ans %mod)
### BUGGY CODE ###

from collections import deque


def BFS():
    point=0
    color=[["white" for _ in range(w)] for _ in range(h)]
    D=[[0 for _ in range(w)] for _ in range(h)]

    queue=deque([])
    for i in range(h):
        for j in range(w):
            if A[i][j]=="#":
                color[i][j]="gray"
                queue.append([i,j])
                D[i][j]=0

    while len(queue)>0:
        x,y=queue.popleft()
        for a,b in [[1,0],[-1,0],[0,1],[0,-1]]:
            X,Y=x+a,y+b
            if 0<=X<h and 0<=Y<w:
                if color[X][Y]!="black":
                    color[X][Y]="gray"
                    D[X][Y]=D[x][y]+1
                    point=max(point,D[X][Y])
                    queue.append([X,Y])
        color[x][y]="black"

    return point


h,w=map(int,input().split())
A=[list(input()) for _ in range(h)]
print(BFS())

### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**7)
inf=10**7


def BFS():
    color=[["white" for _ in range(w+2)] for _ in range(h+2)]
    D=[[inf for _ in range(w+2)] for _ in range(h+2)]

    queue=deque([])
    for i in range(1,h+1):
        for j in range(1,w+1):
            if A[i][j]=="#":
                queue.append([i,j])
                D[i][j]=0
                color[i][j]="gray"

    cnt=0
    while len(queue)!=0:
        a,b=queue.popleft()
        for c,d in ((1,0),(0,1),(-1,0),(0,-1)):
            X,Y=a+c,b+d
            if A[X][Y]=="." and color[X][Y]=="white":
                color[X][Y]="gray"
                D[X][Y]=D[a][b]+1
                cnt=max(cnt,D[X][Y])
                queue.append([X,Y])
        color[a][b]="black"

    return cnt


h,w=map(int,input().split())
A=[["#"]+list(input())+["#"] for _ in range(h)]
A.insert(0,["#"]*(w+2))
A.append(["#"]*(w+2))
print(BFS())
### BUGGY CODE ###

import math
def sieve_advance(n):  #n未満の整数iについてi以下でiを割り切る最小の素数を求める。
    minfactor=[-1]*n
    minfactor[0],minfactor[1]=0,1
    isprime=[True]*n
    isprime[0],isprime[1]=False,False

    for i in range(2,n):
        if isprime[i]:
            minfactor[i]=i
            for j in range(i**2,n,i):
                isprime[j]=False
                if minfactor[j]==-1:
                    minfactor[j]=i
    
    return minfactor

minfactor=sieve_advance(10**6+1)
from collections import defaultdict
def prime_factor(n): #nをminfactorを利用して素因数分解する
    res=defaultdict(int)
    while n!=1:
        prime=minfactor[n]
        exp=0
        while minfactor[n]==prime:
            exp+=1
            n//=prime
        res[prime]=exp

    return res

n=int(input())
nums=list(map(int,input().split()))
mod=10**9+7

factor=[[] for _ in range(n)]
lcm=defaultdict(int)
for i in range(n):
  num=nums[i]
  factor[i]=prime_factor(num)
  for p in factor[i].keys():
    e=factor[i][p]
    lcm[p]=max(lcm[p],e)
#print(lcm)

b=[1]*n
for p in lcm.keys():
  e_lcm=lcm[p]
  for i in range(n):
    e_a=factor[i][p]
    b[i]*=p**(e_lcm-e_a) 
    b[i]%=mod
    
#print(b)
print(sum(b)%mod)

### FIXED CODE ###

def main():
  def sieve(n):
    prime=[]
    limit=n*0.5
    data=[i+1 for i in range(1,n)]
    p_append=prime.append
    while True:
        p=data[0]
        if limit<=p:
            return prime+data
        p_append(p)
        data=[e for e in data if e%p!=0]
        
  prime=sieve(1000)
  import sys
  import numpy as np
  input=sys.stdin.readline
  mod=10**9+7
  
  n=int(input())
  num=list(map(int,input().split()))
  num_copy=np.array(num)
  
  lcm=1
  for p in prime:
    while np.any(num_copy%p==0):
      num_copy[num_copy%p==0]//=p
      lcm *= p
      lcm %= mod
  
  for i in set(num_copy.tolist()):
    lcm *= i
    lcm %= mod
    
  #print(lcm,num)
  ans=0
  for i in range(n):
    ans += lcm * pow(num[i] ,mod-2 ,mod)
    ans %= mod 
    #print(ans)
  print(ans)
  
if  __name__=='__main__':
  main()
### BUGGY CODE ###

import sys
from collections import defaultdict
readline = sys.stdin.readline
N, = map(int, readline().split())
def con(ll):
    rs = []
    for u, v in zip(ll,ll[1:]):
        u, v = sorted([u,v])
        rs.append(100*u+v)
    return set(rs)

def process():
    G = [[] for _ in range(N+1)]
    for v in range(N-1):
        a, b = map(int, readline().split())
        G[a].append(b)
        G[b].append(a)
    M, = map(int, readline().split())
    qs = set()
    ss = set()
    for _ in range(M):
        u, v = sorted(map(int, readline().split()))
        qs.add((u,v))
        ss.add(u)
    dep = dict()
    for i in ss:
        path = []
        stack = [i]
        vs = set([i])
        while stack:
            v = stack.pop()
            if v > 0:
                vs.add(v)
#                parent = path[-1]
                path.append(v)
                for u in G[v]:
                    if u in vs:
                        continue
                    if (i,u) in qs:
                        dep[(i,u)] = con(path+[u])
                    stack += [-v, u]
            else:
                path.pop()
    qs = list(qs)
    r = 0
    for i in range(1,2**M):
        t = 0
        ns = set()
        for j in range(M):
            if i % 2:
                ns = ns | dep[qs[j]]
                t += 1
            i = i>>1
        xx = (1 if t%2 else -1)*2**(N-1-len(ns))
        r += xx
    print(2**(N-1)-r)
if __name__ == '__main__':
    process()


### FIXED CODE ###

import sys
from collections import defaultdict
readline = sys.stdin.readline
N, = map(int, readline().split())
def con(ll,E):
    r = 0
    for u, v in zip(ll,ll[1:]):
        u, v = sorted([u,v])
        r += 1<<E[(u,v)]
    return r

def process():
    G = [[] for _ in range(N+1)]
    E = dict()
    for i in range(N-1):
        a, b = sorted(map(int, readline().split()))
        G[a].append(b)
        G[b].append(a)
        E[(a,b)] = i

    M, = map(int, readline().split())
    qes = dict()
    for _ in range(M):
        u, v = sorted(map(int, readline().split()))
        if u not in qes:
            qes[u] = list()
        qes[u].append(v)
    dep = []
    for i in qes:
        ms = qes[i]
        path = []
        stack = [i]
        vs = set([i])
        while stack:
            v = stack.pop()
            if v > 0:
                vs.add(v)
#                parent = path[-1]
                path.append(v)
                for u in G[v]:
                    if u in vs:
                        continue
                    if u in ms:
                        dep.append(con(path+[u],E))
                    stack += [-v, u]
            else:
                path.pop()
    r = 0
    for i in range(1,2**M):
        t = 0
        ns = 0
#        lns = 
        for j in range(M):
            if i % 2:
                ns = ns | dep[j]
                t += 1
            i = i>>1
        xx = (1 if t%2 else -1)*2**(N-1-bin(ns).count("1"))
        r += xx
    print(2**(N-1)-r)
if __name__ == '__main__':
    process()
### BUGGY CODE ###

import sys
input=sys.stdin.readline
def main():
    s=tuple(input())
    t=tuple(input())
    n=len(s)
    m=len(t)
    dp=[['' for i in range(m+1)] for j in range(n+1)]
    for i in range(n):
        for j in range(m):
            if s[i]==t[j]:
                dp[i+1][j+1]=dp[i][j]+s[i]
            else:
                if len(dp[i+1][j])>len(dp[i][j+1]):
                    dp[i+1][j+1]=dp[i+1][j]
                else:
                    dp[i+1][j+1]=dp[i][j+1]
    print(dp[n][m])
if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
input=sys.stdin.readline
def main():
    s=tuple(input())
    t=tuple(input())
    n=len(s)
    m=len(t)
    dp=[[0 for i in range(m+1)] for j in range(n+1)]
    for i in range(n):
        for j in range(m):
            if s[i]==t[j]:
                dp[i+1][j+1]=dp[i][j]+1
            else:
                if dp[i+1][j]>dp[i][j+1]:
                    dp[i+1][j+1]=dp[i+1][j]
                else:
                    dp[i+1][j+1]=dp[i][j+1]
    p=dp[n][m]
    ans=['' for _ in range(p)]
    n-=1
    m-=1
    while p>0:
        if s[n]==t[m]:
            ans[p-1]=s[n]
            n-=1
            m-=1
            p-=1
        elif dp[n+1][m+1]==dp[n][m+1]:
            n-=1
        else:
            m-=1
    print(''.join(ans)) 
if __name__=='__main__':
    main()
### BUGGY CODE ###

n,m = map(int,input().split())
l = [0] * m
r = [0] * m
for i in range(0,m):
	l[i], r[i] = map(int, input().split())
			
count = 0
for i in range(1,n+1):
	ok_count = 0
	for j in range(0,len(l)):
		if l[j] <= i <= r[j]:
			ok_count += 1
			
		if ok_count == len(l):
			count += 1
			
print(count)
		

### FIXED CODE ###

n,m = map(int,input().split())
l = [0] * m
r = [0] * m
for i in range(0,m):
	l[i], r[i] = map(int, input().split())

count = 0

max_l = max(l)
min_r = min(r)

for i in range(1,n+1):
	
	if max_l <= i <= min_r:
		count += 1
			
print(count)
### BUGGY CODE ###

from collections import Counter

def main():

  s=input()
  n=len(s)
  res=0
  t=[0]*(n+1)
  k=1
  for i in range(1,n+1):
      t[n-i]=(t[n-i+1]+int(s[n-i])*(k%2019))%2019
      k*=10
  d=Counter(t)
  for i in d.values():
      if i<2:
        continue
      res+=i*(i-1)/2
  print(int(res))

if __name__ == '__main__':
  main()


### FIXED CODE ###

from collections import Counter

def main():

  s=input()
  n=len(s)
  res=0
  t=[0]*(n+1)
  k=1
  for i in range(1,n+1):
      t[n-i]=(t[n-i+1]+int(s[n-i])*k)%2019
      k*=10
      k=k%2019
  d=Counter(t)
  for i in d.values():
      if i<2:
        continue
      res+=i*(i-1)/2
  print(int(res))

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

S=input()
N=len(S)
K=int(input())

ans=set([])
for i in range(1,N+1):
    j=0
    while j+i<=N:
        ans.add(S[j:j+i])
        j+=1
ans=sorted(list(ans))
print(ans[K-1])

### FIXED CODE ###

S=input()
N=len(S)
K=int(input())
A=[]
for i in range(1,K+1):
    j=0
    while j+i<=N:
        A.append(S[j:j+i])
        j+=1
A=list(set(A))
A.sort()
print(A[K-1])
### BUGGY CODE ###

def resolve():
    '''
    code here
    '''
    import collections

    H, W = map(int, input().split())
    Ch, Cw = map(lambda x: int(x) - 1, input().split())
    Dh, Dw = map(lambda x: int(x) - 1, input().split())
    grid = [[item for item in input()] for _ in range(H)]
    max_num = 10**6
    fp = [[max_num for _ in range(W)] for _ in range(H)]
    
    que = collections.deque([[Ch, Cw, 0]])
    fp[Ch][Cw] = 0
    next_y_x = []
    for i in range(5):
        for j in range(5):
            next_y_x.append([-2 + i, -2 + j])
    next_y_x.remove([0,0])

    while que:
        y, x, w_num = que.popleft()

        for dy, dx in next_y_x:
            ny = y + dy
            nx = x + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1:
                if abs(dy) + abs(dx) == 1:
                    if grid[ny][nx] == '.' and fp[ny][nx] > w_num:
                        que.appendleft([ny, nx, w_num])
                        fp[ny][nx] = w_num
                else:
                    nw = w_num +1
                    if grid[ny][nx] == '.' and fp[ny][nx] > nw:
                        que.append([ny, nx, nw])
                        fp[ny][nx] = nw

    if fp[Dh][Dw] != max_num:
        print(fp[Dh][Dw])
    else:
        print(-1)

if __name__ == "__main__":
    resolve()


### FIXED CODE ###

def resolve():
    '''
    code here
    '''
    from collections import deque

    H, W = [int(item) for item in input().split()]
    Ch, Cw = [int(item)-1 for item in input().split()]
    Dh, Dw = [int(item)-1 for item in input().split()]
    grid = [input() for _ in range(H)]
    max_num = 10**6
    fp = [[max_num] * W for _ in range(H)]

    que = deque([[Ch, Cw, 0]])
    fp[Ch][Cw] = 0

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    while que:
        y, x, w_num = que.popleft()

        for dy, dx in walk:
            ny = y + dy
            nx = x + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1 and grid[ny][nx] == '.' and fp[ny][nx] > w_num:
                que.appendleft([ny, nx, w_num])
                fp[ny][nx] = w_num

        for dy, dx in warp:
            ny = y + dy
            nx = x + dx
            nw = w_num +1

            if 0 <= ny <= H-1 and 0 <= nx <= W-1 and grid[ny][nx] == '.' and fp[ny][nx] > nw:
                que.append([ny, nx, nw])
                fp[ny][nx] = nw

    if fp[Dh][Dw] != max_num:
        print(fp[Dh][Dw])
    else:
        print(-1)

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

n = int(input())

def lucas(x):
    if x == 0:
        return 2
    elif x == 1:
        return 1
    else:
        return lucas(x-1) + lucas(x-2)

print(lucas(n))

### FIXED CODE ###

n = int(input())

def luc(x):
    x1 = 2
    x2 = 1
    if x == 1:
        return x1
    elif x == 2:
        return x2
    else:
        for i in range(x-2):
            x1,x2 = x2, x1 + x2
        return x2

print(luc(n+1))
### BUGGY CODE ###

_temp = []
my_max = []

size = int(input().rstrip())
for i in range(size):
    try:
        _temp.append(int(input()))
    except EOFError:
        continue

for i, val in enumerate(_temp[:-1]):
    my = max(_temp[i + 1:]) - val
    if i == 0:
        my_max.append(my)
    else:
        if my > max(my_max):
            my_max.append(my)

print(max(my_max))

### FIXED CODE ###

_temp = []

size = int(input().rstrip())
for i in range(size):
    try:
        _temp.append(int(input()))
    except EOFError:
        continue

my_max = -20000000000000
my_min = _temp.pop(0)


for val in _temp:
    my_max = max(my_max, (val - my_min))
    my_min = min(my_min, val)

print(my_max)
### BUGGY CODE ###

h,w=map(int, input().split())
cnt = 0
if h==1 or w == 1:
    print(1)
    exit(0)
    
for i in range(1, w+1):
    cnt += h//2 + (i%2 if h%2!=0 else 0)

print(cnt)

### FIXED CODE ###

h, w = map(int, input().split())
hdiv = h // 2
hmod = h % 2
if h==1 or w==1:
    print(1)
elif hmod == 0:
    print(hdiv * w)
else:
    print(hdiv * w + w // 2 + w % 2)
### BUGGY CODE ###

import os, sys, re, math

(N, Q) = [int(n) for n in input().split()]
S = input()

L = []
R = []
for i in range(Q):
    (l, r) = [int(n) for n in input().split()]
    L.append(l - 1)
    R.append(r)

for i in range(Q):
    substr = S[L[i]:R[i]]
    replaced = re.sub('AC', '', substr)
    print((len(substr) - len(replaced)) >> 1)


### FIXED CODE ###

import os, sys, re, math

(N, Q) = [int(n) for n in input().split()]
S = input()

oc = [0]
n = 0
for i in range(len(S) - 1):
    if S[i:i+2] == 'AC':
        n += 1
    oc.append(n)
oc.append(n)

for i in range(Q):
    (l, r) = [int(n) for n in input().split()]
    print(oc[r - 1] - oc[l - 1])
### BUGGY CODE ###

def main():
    N = int(input())
    A = list(map(int,input().split()))
    B = list(set(A))
    ans = 0
    for v in B:
        tmp = A.count(v)
        if tmp < v:
            ans += tmp
        else:
            ans += tmp-v
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import defaultdict
def main():
    N = int(input())
    d = defaultdict(int)
    ans = 0
    for a in tuple(map(int,input().split())):
        d[a] += 1
    for v in d.items():
        if v[0] > v[1]:
            ans += v[1]
        else:
            ans += v[1]-v[0]
    print(ans)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

def make_divisors(n):
    i = 1
    flg = True
    while i*i <= n:
        if n % i == 0:
            if i in s1:
                flg = False
                break
            if i != n // i:
                if n//i in s1:
                    flg = False
                    break
        i += 1
    return flg

n = int(input())
a = list(map(int,input().split()))
s = set(a)
cnt = 0
from collections import Counter
c = Counter(a)
for i in range(n):
    if c[a[i]] > 1:
        continue
    s1 = s-{a[i]}
    if make_divisors(a[i]):
        cnt += 1
print(cnt)


### FIXED CODE ###

def main():
    n = int(input())
    a = list(map(int,input().split()))
    ans = set(a)
    ma = max(a)
    from collections import Counter
    c = Counter(a)
    for i in range(n):
        t = a[i]
        if c[t] > 1 and t in ans:
            ans.remove(t)
            continue
        j = 2
        tmp = t*j
        while tmp <= ma:
            if tmp in ans:
                ans.remove(tmp)
            j += 1
            tmp = t*j
    print(len(ans))

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

#!/usr/bin/env python3
#ABC128 E

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,q = LI()
stx = [LI() for _ in range(n)]
stx.sort(key = itemgetter(2))
d = [I() for _ in range(q)]
ans = [-1]*q
for s,t,x in stx:
    l,r = bl(d,s-x),bl(d,t-x)
    for i in range(l,r):
        if ans[i] != -1:
            continue
        ans[i] = x
print(*ans)


### FIXED CODE ###

#!/usr/bin/env python3
#ABC128 E

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,q = LI()
stx = [LI() for _ in range(n)]
stx.sort(key = itemgetter(2))
d = [I() for _ in range(q)]
ans = [-1]*(q+1)
right = [0]*q
for s,t,x in stx:
    l,r = bl(d,s-x),bl(d,t-x)
    #l≦d<rを満たすdがxでぶつかる
    #各dにおいて一番最初にぶつかるxを求めたい
    while l < r:
        while ans[l] != -1:
            l = right[l]
        if r <= l:
            break
        ans[l] = x
        right[l] = r
        l += 1
for i in ans[:-1]:
    print(i)
### BUGGY CODE ###

import itertools

if __name__ == "__main__":
    N = int(input())
    A = input().split()
    for x in range(N):
        tmp = [y for idx, y in enumerate(A) if idx != x]
        result = list(filter(lambda t: t[0] == t[1], list(itertools.combinations(tmp, 2))))
        print(len(result))


### FIXED CODE ###

import sys
import itertools
from collections import Counter
sys.setrecursionlimit(10**8)
if __name__ == "__main__":
    N = int(input())
    A = input().split()
    counter = Counter(A)
    result = 0
    for c in counter.values():
        result += c*(c-1)//2
    for a in A:
        k = counter[a]
        print(result - k*(k-1)//2 + (k-1)*(k-2)//2)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys
args = sys.argv

debug_flg = False
def debug(val1,val2="",val3="",val4=""):
    global debug_flg
    if debug_flg:
        print(val1,val2,val3,val4,sep=" , ")

if len(args) != 2:
    n= int(input())
    s= input()
else:
    debug_flg = True
    if args[1] == "2":
        n=39
        s="RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB"
    else:
        n=4
        s="RRGB"

ret =0
for i in range(1,n-1):
    for j in range(i,n):
        if s[i-1] == s[j-1]:
            continue
        for k in range(j,n+1):
            if j-i == k-j:
                continue
            if s[i-1] == s[k-1]:
                continue
            if s[j-1] == s[k-1]:
                continue
            ret += 1

print(ret)


### FIXED CODE ###

def main():
    n= int(input())
    s= input()

    r = s.count("R")
    g = s.count("G")
    b = s.count("B")

    ans = r * g * b
    snum = tuple(s[:])
    for i in range(1,n-1):
        for j in range(i,n):
            k = j * 2 - i
            if k > n:
                break

            if snum[i-1] != snum[j-1] and snum[i-1] != snum[k-1] and snum[j-1] != snum[k-1]:
                ans -= 1

    print(ans)


if __name__ == '__main__':
    main()