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

n,x,y=map(int, input().split())
es=[[] for _ in range(n)]
for i in range(n):
    if i<n-1:
        es[i].append([1,i+1])
    if i>0:
        es[i].append([1,i-1])
    es[x-1].append([1,y-1])
    es[y-1].append([1,x-1])

import heapq

def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in es[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in es[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

from collections import defaultdict, Counter

ans=defaultdict(int)
dists=[]
for i in range(n-1):
    a=dijkstra_heap(i)[i+1:]
    c=Counter(a)
    dists.append(c)
    
for i in range(len(dists)):
    for d in dists[i].keys():
        ans[d]+=dists[i][d]

for i in range(1,n):
    print(ans[i])


### FIXED CODE ###

n,x,y=map(int, input().split())
es=[[] for _ in range(n)]
for i in range(n):
    if i<n-1:
        es[i].append([1,i+1])
    if i>0:
        es[i].append([1,i-1])
    es[x-1].append([1,y-1])
    es[y-1].append([1,x-1])

import heapq

def dijkstra_heap(s):
    d = [float("inf")] * n
    used = [True] * n
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in es[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in es[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

from collections import defaultdict, Counter
from copy import deepcopy
dist=dijkstra_heap(0)
distx=dijkstra_heap(x-1)
disty=dijkstra_heap(y-1)
counts=[]
for i in range(n-1):
    if i<x-1:
        tmp=[d-i for d in dist[i:]]
        counts.append(Counter(tmp))
    elif x-1<=i<y-1:
        tmp=[min(distx[i]+distx[d], disty[i]+disty[d], abs(d-i)) for d in range(i,n)]
        counts.append(Counter(tmp))
    else:
        tmp=[disty[d]-disty[i] for d in range(i,n)]
        counts.append(Counter(tmp))
ans=defaultdict(int)

for i in range(n-1):
    keys=counts[i].keys()
    for kk in keys:
        ans[kk]+=counts[i][kk]

for i in range(1,n):
    print(ans[i])
### BUGGY CODE ###

"""
n = (m*k+1)*(k^l) となるm,lがあるか？

kはnの約数 or n%k==1が必要
"""
 
def is_f(k,n):
    while n%k==0:
        n /= k
    return n%k==1


n = int(input())

cnt = 0
for k in range(2,n+1):
    if n%k == 0 or n%k ==1:
        if is_f(k,n):
            cnt += 1
            
print(cnt)


### FIXED CODE ###

"""
n = (m*k+1)*(k^l) となるm,lがあるか？

kは「nの約数 or n%k==1<=>kがn-1の約数」が必要
"""
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    # divisors.sort()
    return divisors
 
def is_f(k,n):
    while n%k==0:
        n /= k
    return n%k==1


n = int(input())

cnt = 0
num = tuple(make_divisors(n)[1:] + make_divisors(n-1)[1:])

for k in num:
    if is_f(k,n):
        cnt += 1

print(cnt)
### BUGGY CODE ###

x = int(input())

count = 0
for i in range(0, x):
    a =  int(input())
    if a % 2 == 0 and a != 2:
        count += 1
    elif a % 3 == 0 and a != 3:
        count += 1
    else:
        c =int((a + 1) / 2)
        for j in range ( 3,  c-1 ):
            if a % j == 0:
                count += 1
                break;
        
print(x-count)
        



### FIXED CODE ###

x = int(input())

count = 0
for i in range(0, x):
    a =  int(input())
    for j in range ( 2,  a ):
        c = int(a)
        if a % j == 0:
            count += 1
            break;
        if j * j  > c:
            break;
        
print(x-count)
### BUGGY CODE ###

quest = []
N, Q = input().split()
N = int(N)
Q = int(Q)
S = input()
for _ in range(Q):
    tmp = []
    s, e = input().split()
    tmp.append(int(s))
    tmp.append(int(e))
    quest.append(tmp)

for i in range(Q):
    print(S.count('AC', quest[i][0]-1, quest[i][1]))




### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
ans = [0]*(N+1)
for i in range(N):
    ans[i+1] = ans[i]
    if S[i: i+2] == 'AC':
        ans[i+1] += 1
for _ in range(Q):
    start, end = map(int, input().split())
    cnt = ans[end-1] - ans[start-1]
    print(cnt)
### BUGGY CODE ###

import collections

N,K,Q = map(int,input().split())
A = [int(input()) for i in range(Q)]
c = collections.Counter(A)

if (K - Q) > 0:
    for _ in range(N):
        print('Yes')
else:
    l = []
    for i,v in sorted(dict(c).items(),reverse = True, key=lambda x:x[1]):
        if v >(Q - K):
            l.append(i-1)
        else:
            break
    for j in range(N):
        if j in l:
            print('Yes')
        else:
            print('No')

### FIXED CODE ###

import collections

N,K,Q = map(int,input().split())
A = [int(input()) for i in range(Q)]
c = collections.Counter(A)

if (K - Q) > 0:
    for _ in range(N):
        print('Yes')
else:
    l = ['No'] * N
    for i,v in dict(c).items():
        if v >(Q - K):
            l[i-1] = 'Yes'
    for j in l:
        print(j)
### BUGGY CODE ###

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

### FIXED CODE ###

def main():
    n, k, *h = map(int, open(0).read().split())
    dp = [float('inf')] * n
    dp[0] = 0
    for i in range(1, n):
        min_i = max(0, i-k)
        dp[i] = min([dp[j] + abs(h[i] - h[j]) for j in range(min_i, i)])
    print(dp[n-1])
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import bisect

input()
A=sorted([int(i) for i in input().split()])
B=sorted([int(i) for i in input().split()])
C=sorted([int(i) for i in input().split()])

ans=0
for a in A:
  for b in B[bisect.bisect_right(B,a):]:
    ans+=len(C[bisect.bisect_right(C,b):])

print(ans)

### FIXED CODE ###

import bisect

N=int(input())
A=sorted([int(i) for i in input().split()])
B=sorted([int(i) for i in input().split()])
C=sorted([int(i) for i in input().split()])

ans=0
for b in B:
  ans+=bisect.bisect_left(A,b)*(N-bisect.bisect_right(C,b))

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

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


def cake(i, used, x, y, z):
    if i <= N and used >= M:
        return abs(x) + abs(y) + abs(z)
    if i >= N:
        return 0
    r = cake(i+1, used, x, y, z)
    r = max(r, cake(i+1, used+1, x+xyz[i][0], y+xyz[i][1], z+xyz[i][2]))
    return r


ans = cake(0, 0, 0, 0, 0)
print(ans)


### FIXED CODE ###

N, M = map(int, input().split())
xyz = []
ans = 0
for _ in range(N):
    xyz += [list(map(int, input().split()))]
for b in range(2 ** 3):
    pm = [1] * 3
    for j in range(3):
        if (b >> j) & 1:
            pm[j] *= -1
    r = []
    for i in range(N):
        r += [pm[0] * xyz[i][0] + pm[1] * xyz[i][1] + pm[2] * xyz[i][2]]
    r.sort(reverse=True)
    ans = max(ans, sum(r[:M]))
print(ans)
### BUGGY CODE ###

N=int(input())
S=input()
b=0
for i in range(1000):
 a=0
 i1=int(i/100)
 i2=int((i-i1*100)/10)
 i3=i%10
 for j in range(N-2):
  if int(S[j])==i1:
   for k in range(j+1,N-1):
    if int(S[k])==i2:
     for l in range(k+1,N):
      if int(S[l])==i3:
       a+=1
       break
     else:
      continue
     break
   else:
    continue
   break
 if a>0:
  b+=1
print(b)

### FIXED CODE ###

N=int(input())
S=input()
A=[0]*N
for i in range(N):
 A[i]=int(S[i])
b=0
for i in range(1000):
 i1=int(i/100)
 i2=int((i-i1*100)/10)
 i3=i%10
 a=0
 for j in range(N):
  if a==0:
   if A[j]==i1:
    a+=1
  elif a==1:
   if A[j]==i2:
    a+=1
  else:
   if A[j]==i3:
    b+=1
    break
print(b)
### BUGGY CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

from bisect import bisect_left, bisect_right

n, d, a = map(int, input().split())
x = []
xh =dict()
for _ in range(n):
    xi, hi = map(int, input().split())
    x.append(xi)
    xh[xi] = hi
x.sort()

l = 0
ret = 0
while l < n:
    xl = x[l]
    hl = xh[xl]
    l += 1
    if hl <= 0:
        continue
    r = bisect_right(x, xl+2*d)
    k = (hl+(a-1))//a
    ret += k
    for i in range(l, r):
        xh[x[i]] -= k * a
print(ret)


### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

from bisect import bisect_left, bisect_right

n, d, a = map(int, input().split())
x = []
xh = dict()
for _ in range(n):
    xi, hi = map(int, input().split())
    x.append(xi)
    xh[xi] = hi
x.sort()

l = 0
ret = 0
ai = [0] * (n+1)
anow = 0
while l < n:
    xl = x[l]
    hl = xh[xl]
    anow += ai[l]
    hl -= a * anow
    if hl > 0:
        r = bisect_right(x, xl+2*d)
        k = (hl+(a-1))//a
        ret += k
        anow += k
        ai[r] -= k
    l += 1
print(ret)
### BUGGY CODE ###

R,G,B,N = map(int,input().split())
cnt = 0
for r in range(3001):
    for g in range(3001):
        V = r * R + g * G 
        if N >= V and (N - V) % B == 0:
            cnt += 1
        else:
            continue
print(cnt)

### FIXED CODE ###

R,G,B,N = map(int,input().split())
cnt = 0
for r in range((N // R) + 1):
    for g in range((N - (r * R)) // G + 1):
        V = N - (r * R + g * G)
        if V >= 0 and V % B == 0:
            cnt += 1
print(cnt)
### BUGGY CODE ###

a, b, n = map(int, input().split())
ans = 0
for x in range(1,n+1):
    B = x/b
    f = B - int(B) 
    if ans <= f:
        ans = f
print(int(ans * a))

### FIXED CODE ###

a, b, n = map(int, input().split())
M = min(b-1,n)
print(int((M/b-M//b) * a))
### BUGGY CODE ###

S = str(input())
Q = int(input())

topFlg = True

for _ in range(Q):
    query = list(map(str, input().split()))
    if query[0] == "1":
        topFlg = not (topFlg)
    else:
        if query[1] == "1":
            S = query[2] + S if topFlg else S + query[2]
        else:
            S = S + query[2] if topFlg else query[2] + S

print(S) if topFlg else print(S[::-1])


### FIXED CODE ###

S = str(input())
Q = int(input())

topFlg = True

leftStr = ""
rightStr = ""

for _ in range(Q):
    query = list(map(str, input().split()))
    if query[0] == "1":
        topFlg = not (topFlg)
    else:
        if query[1] == "1":
            if topFlg:
                leftStr = query[2] + leftStr
            else:
                rightStr += query[2]
        else:
            if topFlg:
                rightStr += query[2]
            else:
                leftStr = query[2] + leftStr

print(leftStr + S +
      rightStr if topFlg else rightStr[::-1] + S[::-1] + leftStr[::-1])
### BUGGY CODE ###

if __name__ == '__main__':
    from sys import stdin
    # from collections import defaultdict
    # from collections import deque
    # from collections import Counter
    # import numpy as np
    import math
    # import random
    input = stdin.readline

    p = 998244353

    def pow_k(x, n):
        """
        O(log n)
        """
        if n == 0:
            return 1

        K = 1
        while n > 1:
            if n % 2 != 0:
                K *= x
                K = K%p
            x *= x
            n //= 2

        return (K * x)%p

    n, m, k = map(int, input().split())
    if m == 1:
        if k < n-1:
            print(0)
        else:
            print(1)
        exit()

    ans = 0
    first = pow_k(m-1, n-k-1)
    first_cmb = math.factorial(n-1) // math.factorial(k) // math.factorial(n - k-1)
    for i in range(k, -1, -1):
        ans += (first_cmb*first)%p
        first = (first*(m-1))%p
        first_cmb = (first_cmb*i)//(n-i)
    ans = ans*m
    print(ans%p)



### FIXED CODE ###

if __name__ == '__main__':
    from sys import stdin
    # from collections import defaultdict
    # from collections import deque
    # from collections import Counter
    # import numpy as np
    import math
    # import random
    input = stdin.readline

    p = 998244353

    def cmb(n, r, p):
        if (r < 0) or (n < r):
            return 0
        r = min(r, n - r)
        return fact[n] * factinv[r] * factinv[n-r] % p

    # p = 10 ** 9 + 7
    N = 10 ** 6  # N は必要分だけ用意する
    fact = [1, 1]  # fact[n] = (n! mod p)
    factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
    inv = [0, 1]  # factinv 計算用
    
    for i in range(2, N + 1):
        fact.append((fact[-1] * i) % p)
        inv.append((-inv[p % i] * (p // i)) % p)
        factinv.append((factinv[-1] * inv[-1]) % p)

    def pow_k(x, n):
        """
        O(log n)
        """
        if n == 0:
            return 1

        K = 1
        while n > 1:
            if n % 2 != 0:
                K *= x
                K = K%p
            x *= x
            n //= 2

        return (K * x)%p

    n, m, k = map(int, input().split())
    if m == 1:
        if k < n-1:
            print(0)
        else:
            print(1)
        exit()

    ans = 0
    first = pow_k(m-1, n-k-1)
    for i in range(k, -1, -1):
        first_cmb = cmb(n-1, i, p)
        ans += (first_cmb*first)%p
        first = (first*(m-1))%p
        # first_cmb = (first_cmb*i)//(n-i)
        


    ans = ans*m
    print(ans%p)
### BUGGY CODE ###

N = int(input())
S = input()

# 文字とindexのマップ
dic = {}
for i, n in enumerate(S):
    if n not in dic:
        dic[n] = [i]
    else:
        dic[n].append(i)


ret_max = 0
for i in range(N):
    index = []
    temp_max = 0
    for j in range(N):
        # target = S[i:j + 1]
        target = S[i]

        if target in dic:
            idx_lst = dic[target].copy()
            # print(idx_lst, i, target)

            idx_lst.remove(i)

            if idx_lst:
                temp_max = 1
            else:
                temp_max = 0
        else:
            continue

        cnt = 1
        if idx_lst:
            next_idx = idx_lst[0]
        else:
            next_idx = 0
        while idx_lst:
            for idx in idx_lst:
                if j + 1 + cnt <= next_idx and S[idx:idx + 1 + cnt] == S[i:j + 1 + cnt] and idx + 1 + cnt <= N:
                    # print(idx, S[idx:idx + 1 + cnt], S[i:j + 1 + cnt])
                    temp_max = 1 + cnt
                else:
                    idx_lst.remove(idx)

            cnt += 1

        ret_max = max(ret_max, temp_max)


print(ret_max)

### FIXED CODE ###

class RollingHash(object):
    def __init__(self, S, base, mod):
        self.mod = mod
        l = len(S)

        self.hash_lst = [0] * (l + 1)
        self.pow_lst = [1] * (l + 1)

        for i in range(l):
            self.hash_lst[i + 1] = (self.hash_lst[i] * base + ord(S[i])) % mod
            self.pow_lst[i + 1] = (self.pow_lst[i] * base) % mod

    def get_hash(self, left, right):
        return (self.hash_lst[right] - self.hash_lst[left] * self.pow_lst[right - left] % self.mod) % self.mod


N = int(input())
S = input()

base = 1007
mod = pow(10, 9) + 7
rh = RollingHash(S, base, mod)

left = 0
right = N // 2

while left <= right:
    mid = (left + right) // 2

    found_hash = {}
    found = False
    for i in range(N - mid + 1):
        h = rh.get_hash(i, i + mid)

        if h not in found_hash:
            found_hash[h] = i
        else:
            if found_hash[h] <= i - mid:
                found = True
                break

    if found:
        left = mid + 1
    else:
        right = mid - 1


print(right)
### BUGGY CODE ###

N = int(input())
a = []

for i in range(N):
    a.append(int(input()))


count = 0
Sosu = True

for i in range(0,N):
    Sosu = True
    for j in range(2,a[i]):
        if a[i] % j == 0:
            Sosu = False
            break
        else :
            pass
    if Sosu :
        count+=1
    else:
        pass


print(count)







### FIXED CODE ###

N = int(input())
a = []

count = 0
for i in range(N):
    x=int(input())
    if x == 2:
        count+=1
    else:
        if pow(2, x-1,x ) == 1:
            count+=1
        else:
            pass

print(count)
### BUGGY CODE ###

def main():
    N  = int(input()) 
    A=list(map(int, input().split()))
    B = list(set(A))
    B.sort(reverse=True)
    cnt = 0
    for i in range(len(B)):
        if A.count(B[i])>1:
            continue
        Flag = True
        for j in range(i+1,len(B)):
            if B[i] % B[j] == 0:
                Flag = False
                break
        if Flag:
            cnt += 1
    
    print(cnt)



if __name__ == '__main__':
    main()

### FIXED CODE ###

import collections

def main():
    N  = int(input()) 
    A=list(map(int, input().split()))
    C = collections.Counter(A)
    B = list(set(A))
    B.sort()
    lenb = len(B)
    Boo = [True]*lenb
    ZENBU = [False]*(10**6+4)

    if C[1]>1:
        print(0)
        return
    if C[1]==1:
        print(1)
        return

    for i in range(lenb):
        temp = 2
        if ZENBU[B[i]]==False:
            while B[i]*temp < 1000002:
                ZENBU[B[i]*temp] = True
                temp+=1

    cnt = 0
    for i in range(lenb):
        if ZENBU[B[i]]==False and C[B[i]]==1:
            cnt += 1

    print(cnt)


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

import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    R, C, K = NMI()
    item = {(0,0):0}

    for i in range(K):
        r_, c_, v_, = NMI()
        item[(r_ - 1,c_ - 1)] = v_

    dp = [[[0 for _ in range(4)] for _ in range(C + 2)] for _ in range(R + 2)]

    for i in range(R + 1):
        for j in range(C + 1):
            for k in range(4):
                if (i,j) in item:
                    v = item[(i,j)]
                else:
                    v = 0

                if k == 3:
                    dp[i + 1][j][0] = max(dp[i][j][k], dp[i + 1][j][0])
                    continue
                dp[i + 1][j][0] = max(dp[i][j][k], dp[i][j][k] + v, dp[i + 1][j][0])
                dp[i][j + 1][k] = max(dp[i][j][k], dp[i][j + 1][k])
                dp[i][j + 1][k + 1] = max(dp[i][j][k] + v, dp[i][j + 1][k + 1])

    print(max(dp[R][C][0], dp[R][C][1], dp[R][C][2], dp[R][C][3]))

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid_int(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    R, C, K = NMI()
    grid = make_grid_int(R, C, 0)
    for i in range(K):
        r, c, v = NMI()
        grid[r-1][c-1] = v

    dp = [[[0 for _ in range(C+2)] for _ in range(R+2)] for _ in range(4)]

    for r in range(R+1):
        for c in range(C+1):
            for i in range(4):
                now = dp[i][r][c]
                try:
                    val = grid[r][c]
                except:
                    val = 0

                if i == 3:
                    # 取らずに下
                    dp[0][r + 1][c] = max(now, dp[0][r + 1][c])
                    continue

                # 取って下
                dp[0][r+1][c] = max(now + val, dp[0][r+1][c])
                # 取らずに下
                dp[0][r+1][c] = max(now, dp[0][r+1][c])
                # 取って横
                dp[i+1][r][c+1] = max(now + val, dp[i+1][r][c+1])
                # 取らずに横
                dp[i][r][c+1] = max(now, dp[i][r][c+1])

    print(max(dp[0][R][C], dp[1][R][C], dp[2][R][C], dp[3][R][C]))


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

#!/usr/bin/env python3
import sys
from functools import reduce
import fractions

MOD = 1000000007  # type: int

GCD_CACHE = {}


def gcd(x, y):
    if (x, y) in GCD_CACHE:
        return GCD_CACHE[(x, y)]
    d = fractions.gcd(x, y)
    GCD_CACHE[(x, y)] = d
    return d


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


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


def solve(N: int, A: "List[int]"):
    m = lcm(*A)
    sum = 0
    for a in A:
        sum = (sum + m//a) % MOD
    print(sum)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from functools import reduce
import fractions

MOD = 1000000007  # type: int

GCD_CACHE = {}


def gcd(x, y):
    if (x, y) in GCD_CACHE:
        return GCD_CACHE[(x, y)]
    d = fractions.gcd(x, y)
    GCD_CACHE[(x, y)] = d
    return d


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


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


def solve(N: int, A: "List[int]"):
    m = lcm(*A) % MOD
    sum = 0
    for a in A:
        sum = (sum + m*pow(a, MOD-2, MOD)) % MOD
    print(sum)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


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

from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n = int(input())
    s = list(input()[:-1].decode())
    r = []
    g = []
    b = []
    for i in range(n):
        if s[i] == 'R':
            r.append(i)
        elif s[i] == 'G':
            g.append(i)
        elif s[i] == 'B':
            b.append(i)
    ans = len(r) * len(g) * len(b)

    def check(n):
        return b.count(n) > 0

    for ri in r:
        for gi in g:
            if check(2 * gi - ri):
                ans -= 1
            if check(2 * ri - gi):
                ans -= 1
            if (ri + gi) % 2 == 0 and check((ri + gi) // 2):
                ans -= 1
    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()


### FIXED CODE ###

from sys import stdin


def main():
    n = int(stdin.readline())
    s = stdin.readline()[:-1]

    nr = 0
    ng = 0
    nb = 0
    nn = 0

    for i in range(n):
        if s[i] == 'R':
            nr += 1
        elif s[i] == 'G':
            ng += 1
        elif s[i] == 'B':
            nb += 1
        for j in range(i + 1, n):
            k = j + j - i
            if 0 <= k < n and s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
                nn += 1

    print(nr * ng * nb - nn)


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

import numpy as np

R,C,K=map(int,input().split())
V=np.zeros((R,C),dtype=np.int64)

for i in range(K):
    r,c,v=map(int,input().split())
    V[r-1][c-1]=v

dp=np.zeros((C+1,4),dtype=np.int64)
for i in range(R):
    ndp=np.zeros((C+1,4),dtype=np.int64)
    for j in range(C):
        ndp[j][0]=max(dp[j])

    for j in range(C):
        v=V[i][j]
        for n in range(1,4):
            ndp[j][n]=max(ndp[j-1][n-1]+v,dp[j][3]+v,ndp[j-1][n])

    dp=ndp

print(max(dp[C-1]))


### FIXED CODE ###

R,C,K=map(int,input().split())

V=[[0 for _ in range(C)] for _ in range(R)]

for i in range(K):
    r,c,v=map(int,input().split())
    V[r-1][c-1]=v

dp=[[0 for _ in range(4)] for _ in range(C+1)]
for i in range(R):
    ndp=[[0 for _ in range(4)] for _ in range(C+1)]
    for j in range(C):
        ndp[j][0]=max(dp[j])

    for j in range(C):
        v=V[i][j]
        for n in range(1,4):
            ndp[j][n]=max(ndp[j-1][n-1]+v,dp[j][3]+v,ndp[j-1][n])

    dp=ndp

print(max(dp[C-1]))