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

import sys
MX = 10**5
def main():
    data = map(int, sys.stdin.buffer.read().split())
    N = next(data)
    IV, IW = [], []

    H = min(N + 1, 1 << 10)
    Hb = (H - 1).bit_length()
    dp = [None for _ in range(H)]
    dp[0] = [0] * (MX + 1)
    for i in range(1, min(N + 1, H)):
        v, w = next(data), next(data)
        dpi = dp[i >> 1][:]
        dp[i] = dpi
        for j in range(MX, w - 1, -1):
            dpi[j] = max(dpi[j], dpi[j - w] + v)
    for i in range(min(N + 1, H), N + 1):
        v, w = next(data), next(data)
        IV.append(v)
        IW.append(w)

    Q = next(data)
    for v, L in zip(data, data):
        if v < H:
            print(dp[v][L])
            continue

        item_values = []
        item_weights = []
        while v >= H:
            item_values.append(IV[v - H])
            item_weights.append(IW[v - H])
            v >>= 1

        l = len(item_values)
        V = [0] * (1 << l)
        W = [0] * (1 << l)
        ans = [dp[v][L]]
        for i in range(1, 1 << l):
            msb = i & (-i)
            msbb = msb.bit_length() - 1
            wi = W[i - msb] + item_weights[msbb]
            W[i] = wi
            if wi <= L:
                vi = V[i - msb] + item_values[msbb]
                ans.append(vi + dp[v][L - wi])
                V[i] = vi
        print(max(ans))

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
MX = 10**5
def main():
    data = map(int, sys.stdin.buffer.read().split())
    N = next(data)

    H = min(N + 1, 1 << 10)
    dp = [None] * H
    dp[0] = [0] * (MX + 1)
    IV, IW = [], []
    i = 1
    for v, w in zip(data, data):
        if i < H:
            dpi = dp[i >> 1][:]
            dp[i] = dpi
            for j in range(MX, w - 1, -1):
                dpi[j] = max(dpi[j], dpi[j - w] + v)
        else:
            IV.append(v)
            IW.append(w)
        i += 1
        if i > N:
            break

    Q = next(data)
    for v, L in zip(data, data):
        if v < H:
            print(dp[v][L])
            continue

        item_values = []
        item_weights = []
        while v >= H:
            item_values.append(IV[v - H])
            item_weights.append(IW[v - H])
            v >>= 1

        l = len(item_values)
        V = [0] * (1 << l)
        W = [0] * (1 << l)
        ans = dp[v][L]
        for i in range(1, 1 << l):
            msb = i & (-i)
            msbb = msb.bit_length() - 1
            wi = W[i - msb] + item_weights[msbb]
            W[i] = wi
            if wi <= L:
                vi = V[i - msb] + item_values[msbb]
                ans = max(ans, vi + dp[v][L - wi])
                V[i] = vi
        print(ans)

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

#!/usr/bin/env python3
import sys


def solve(s: str, K: int):
    n = len(s)
    ss = {
        s[i:j]
        for i in range(n)
        for j in range(i + 1, n + 1)
    }
    print(sorted(ss)[K - 1])


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    K = int(next(tokens))  # type: int
    solve(s, K)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(s: str, K: int):
    n = len(s)
    ss = {
        s[i:j]
        for i in range(n)
        for j in range(i + 1, min(n + 1, i + K + 1))
    }
    print(sorted(ss)[K - 1])
 

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    K = int(next(tokens))  # type: int
    solve(s, K)


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

from scipy.sparse.csgraph import floyd_warshall
n = int(input())
d = [[10**14]*n for i in range(n)]
L = []
dist = []
for i in range(n):
    d[i][i] = 0
for i in range(n):
    L = list(map(int,input().split()))
    dist.append(L)
    for j in range(n):
        d[i][j] = L[j]
        d[j][i] = L[j]
d = floyd_warshall(d)
flag = True
for i in range(n):
  for j in range(n):
    if d[i][j] < dist[i][j]:
      flag = False
      break
if not flag:
  print(-1)
else:
  ans = 0
  for i in range(n):
    for k in range(n):
      for j in range(n):
        if i != k and k != j:
          if d[i][j] == d[i][k]+d[k][j]:
            ans += d[i][j]
  print(int((sum(sum(d))-ans)//2))

### FIXED CODE ###

n = int(input())
d = [[10**16]*n for i in range(n)]
L = []
ans = 0
for i in range(n):
    d[i][i] = 0
for i in range(n):
    L = list(map(int,input().split()))
    for j in range(i+1):
        d[i][j] = L[j]
        d[j][i] = L[j]
        ans += L[j]
flag = True
for i in range(n):
  for j in range(i+1):
    for k in range(n):
      if d[i][j] > d[i][k]+d[k][j]:
        print(-1)
        exit()
      else:
        if d[i][j] == d[i][k]+d[k][j] and i != k and k != j:
          ans -= d[i][j]
          break
print(ans)
### BUGGY CODE ###

N, K = [int(i) for i in input().split()]
a = list(map(int, input().split()))
dp = []


def mincos(dp, a, i, k):
    if i == 0:
        return 0
    elif i < k:
        mincos = 10000000000
        for j in range(1, i + 1):
            if mincos > dp[i - j] + abs(a[i] - a[i - j]):
                mincos = dp[i - j] + abs(a[i] - a[i - j])
        return mincos
    else:
        mincos = 10000000000
        for j in range(1, k + 1):
            if mincos > dp[i - j] + abs(a[i] - a[i - j]):
                mincos = dp[i - j] + abs(a[i] - a[i - j])
        return mincos


for i in range(N):
    dp.append(mincos(dp, a, i, K))

print(dp[N-1])

### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())
h = np.array(list(map(int, input().split())))

dp = np.array([0] * N)

for i in range(1, N):
    j = max(0, i-K)
    dp[i] = (dp[j:i] + np.abs(h[i] - h[j:i])).min()


print(dp[-1])
### BUGGY CODE ###

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

a = []

while N > abs(N-K):
    N = abs(N-K)
    
print(N)

### FIXED CODE ###

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

print(min(N%K, K-N%K))
### BUGGY CODE ###

from bisect import*
n,*a=map(int,open(0).read().split())
l=[0]*n
for i,v in enumerate(a,1):
  l[v-1]=i
b=[0,n+1]
c=0
for i,v in enumerate(l,1):
  j=bisect(b,v)
  c+=(b[j]-v)*(v-b[j-1])*i
  b.insert(j,v)
print(c)

### FIXED CODE ###

root=lambda x:x if par[x]==x else root(par[x])
same=lambda x,y:root(x)==root(y)
def unite(*z):
  x,y=map(root,z)
  if x!=y:
    if rank[x]<rank[y]:
      par[x]=y
      size[y]+=size[x]
    else:
      par[y]=x
      size[x]+=size[y]
      if rank[x]==rank[y]:rank[x]+=1
n,*a=map(int,open(0).read().split())
*par,=range(n)
rank=[1]*n
size=[1]*n
b=[0]*n
for i,t in enumerate(a):b[t-1]=i
c=0
for k in b[::-1]:
  l=r=1
  if k>0 and a[k-1]>a[k]:
    l+=size[root(k-1)]
    unite(k-1,k)
  if k+1<n and a[k+1]>a[k]:
    r+=size[root(k+1)]
    unite(k+1,k)
  c+=l*r*a[k]
print(c)
### BUGGY CODE ###

a=int(input())
Sum=1

for i in range(1,a+1):
    Sum*=i

print(Sum%(10**9+7))


### FIXED CODE ###

a=int(input())
Sum=1
b=10**9+7

for i in range(1,a+1):
    Sum=(Sum*i)%b

print(Sum)
### BUGGY CODE ###

def main():
    import heapq
    n, m, *abc = map(int, open(0).read().split())
    a = abc[:n]
    b = []
    for i, j in zip(*[iter(abc[n:])] * 2):
        b += [j] * i

    c = heapq.merge(a, b)

    print(sum(heapq.nlargest(n, c)))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from collections import Counter
    n, m, *abc = map(int, open(0).read().split())
    a = Counter(abc[:n])
    bc = abc[n:]
    for i, j in zip(*[iter(bc)] * 2):
        a[j] += i

    cnt = n
    ans = 0
    keys = list(a.keys())
    keys.sort(reverse=True)

    for k in keys:
        m = a[k]
        if m <= cnt:
            ans += k * m
            cnt -= m
        else:
            ans += k * cnt
            break

    print(ans)


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

n,m,l=map(int,raw_input().split())
INF=(10**9)+1

g=[]
f=[]
for i in xrange(n):
    g.append([INF]*(n))
    f.append([INF]*(n))

for i in xrange(len(g)):
    for j in xrange(len(g)):
        if i==j:
            g[i][j]=0
            f[i][j]=0

for i in xrange(m):
    a,b,c=map(int,raw_input().split())
    g[a-1][b-1]=c
    g[b-1][a-1]=c
    f[a-1][b-1]=c
    f[b-1][a-1]=c

for k in xrange(n):
    for i in xrange(n):
        for j in xrange(n):
            g[i][j]=min(g[i][j],g[i][k]+g[k][j])
            f[i][j]=min(f[i][j],f[i][k]+f[k][j])

for i in xrange(n):
    for j in xrange(n):
        if f[i][j]<=l:
            g[i][j]=1
        else:
            g[i][j]=INF
        if i==j:
            g[i][j]=0

for k in xrange(n):
    for i in xrange(n):
        for j in xrange(n):
            g[i][j]=min(g[i][j],g[i][k]+g[k][j])

q=int(raw_input())
for i in xrange(q):
    s,t=map(int,raw_input().split())
    u=g[s-1][t-1]

    if u>=INF:
        print (-1)
    else:
        print (u-1)

### FIXED CODE ###

n,m,l=map(int,raw_input().split())
INF=(10**9)+1

g=[]
f=[]
for i in xrange(n):
    g.append([INF]*(n))
    f.append([INF]*(n))

for i in xrange(len(g)):
    for j in xrange(len(g)):
        if i==j:
            g[i][j]=0
            f[i][j]=0

for i in xrange(m):
    a,b,c=map(int,raw_input().split())
    g[a-1][b-1]=c
    g[b-1][a-1]=c
    f[a-1][b-1]=c
    f[b-1][a-1]=c

for k in xrange(n):
    for i in xrange(n):
        for j in xrange(n):
            g[i][j]=min(g[i][j],g[i][k]+g[k][j])
            f[i][j]=min(f[i][j],f[i][k]+f[k][j])

for i in xrange(n):
    for j in xrange(n):
        if f[i][j]<=l:
            g[i][j]=1
        else:
            g[i][j]=INF
        if i==j:
            g[i][j]=0

for k in xrange(n):
    for i in xrange(n):
        for j in xrange(n):
            g[i][j]=min(g[i][j],g[i][k]+g[k][j])

q=int(raw_input())
for i in xrange(q):
    s,t=map(int,raw_input().split())
    u=g[s-1][t-1]

    if u>=INF:
        print (-1)
    else:
        print (u-1)
### BUGGY CODE ###

S = input()
Q = int(input())
flag = True
for i in range(Q):
    que = input()
    if len(que) == 1:
        if flag:
            flag = False
        else:
            flag = True
    else:
        if que[2] == '1':
            if flag:
                S = ''.join([que[4], S])
            else:
                S = ''.join([S, que[4]])
        else:
            if flag:
                S = ''.join([S, que[4]])
            else:
                S = ''.join([que[4], S])
if flag:
    print(S)
else:
    for i in range(len(S)):
        print(S[len(S)-i-1], end = '')
    print()


### FIXED CODE ###

S = input()
T = ''
Q = int(input())
flag = True
for i in range(Q):
    que = input()
    if len(que) == 1:
        if flag:
            flag = False
        else:
            flag = True
    else:
        if que[2] == '1':
            if flag:
                T = T+que[4]
            else:
                S = S+que[4]
        else:
            if flag:
                S = S+que[4]
            else:
                T = T+que[4]
if flag:
    U = ''
    for i in range(len(T)):
        U += T[len(T)-i-1]
    print(U+S)
else:
    U = ''
    for i in range(len(S)):
        U += S[len(S)-i-1]
    print(U+T)
### BUGGY CODE ###

N = int(input())
UVW = [list(map(int, input().split())) for _ in range(N - 1)]

UVW.sort(key = lambda x: x[0])
color = [2 for _ in range(N)]

while len(UVW) > 0:
  uvw = UVW.pop()
  if len(UVW) == N - 2:
    if uvw[2] % 2 == 0:
      color[uvw[0] - 1] = 0
      color[uvw[1] - 1] = 0
    else:
      color[uvw[0] - 1] = 0
      color[uvw[1] - 1] = 1
  if uvw[2] % 2 == 0:
    if color[uvw[0] - 1] != 2:
      color[uvw[1] - 1] = color[uvw[0] - 1]
    elif color[uvw[1] - 1] != 2:
      color[uvw[0] - 1] = color[uvw[1] - 1]
    else:
      UVW.append(uvw)
  else:
    if color[uvw[0] - 1] != 2:
      color[uvw[1] - 1] = color[uvw[0] - 1] ^ 1
    elif color[uvw[1] - 1] != 2:
      color[uvw[0] - 1] = color[uvw[1] - 1] ^ 1
    else:
      UVW.append(uvw)

for c in color:
  print(c)

### FIXED CODE ###

N = int(input())
to = [[] for _ in range(N)]
cost = [[] for _ in range(N)]

for _ in range(N - 1):
  a, b, w = map(int, input().split())
  a -= 1
  b -= 1
  to[a].append(b)
  to[b].append(a)
  cost[a].append(w)
  cost[b].append(w)

ans = [-1 for _ in range(N)]
queue = []
queue.append(0)
while len(queue) > 0:
  v = queue.pop(0)
  for i in range(len(to[v])):
    u = to[v][i]
    w = cost[v][i]
    if ans[u] != -1:
      continue
    ans[u] = (ans[v] + w) % 2
    queue.append(u)

for a in ans:
  print(a)
### BUGGY CODE ###

import numpy as np

N,K,*A = map(int,open(0).read().split())
na = np.array(A)
K = min(K,100)

for i in range(K):
    if all(na) == N:
        break
    B = [0] * N
    nb = np.array(B)
    for n in range(N):
        L = max(0, n-na[n])
        R = min(N-1 , n + na[n])
        nb[L] += 1
        if R+1 != N:
            nb[R+1] -= 1
      
    na = nb.cumsum()        
 
print(*na,sep=" ")    
   


### FIXED CODE ###

from itertools import accumulate
#from operator import add

N,K = map(int,input().split())
A = map(int,input().split()) 
for k in range(K):
    B = [0] * N
    for i,x in enumerate(A):
        L = max(0, i-x)
        R = min(N-1, i+x)
        B[L] += 1
        if R+1 != N:
            B[R+1] -= 1
    #L = accumulate(B,add) 
    L = list(accumulate(B))[:]
    if L == A:
        break
    A = L
print(*A)
### BUGGY CODE ###

n,m = map(int,input().split())#nは品物の数　mは割引券の数
a = sorted(list(map(int,input().split())),reverse = True)#値段一覧
for i in range(m):
    if len(a) == 1:
        a[0] = a[0]//2
        if a[0] == 0:
            print(a[0])
            exit()
    elif a[0] >= a[1]:
        a[0] = a[0]//2
        a.sort(reverse = True)
print(sum(a))

### FIXED CODE ###

import heapq
n,m = map(int,input().split())#nは品物の数　mは割引券の数
a = sorted(list(map(int,input().split())),reverse = True)#値段一覧
a = list(map(lambda x: x*(-1), a))  
heapq.heapify(a)#リストを優先度付きキューへ入れる
highest = 0
ans = []
for i in range(m):
    highest = heapq.heappop(a)*(-1)#heappopでとりだし　heappop(リスト名)*(リストのインデックス)本来最小値を取り出すものである
    heapq.heappush(a,highest//2*(-1))#引数(挿入先リスト名,挿入する数値)
print(sum(a)*-1)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp=[[0]*(W+1) for _ in range(N+1)]
    for i in range(1, N+1):
        for j in range(1,W+1):
            if j>w[i-1]-1:
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1])
            else:
                dp[i][j]=dp[i-1][j]
    print(dp[N][W])
    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
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]"
    v = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp=[[0]*(W+1) for _ in range(N+1)]
    for i in range(1, N+1):
        for j in range(1,W+1):
            if j>w[i-1]-1:
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1])
            else:
                dp[i][j]=dp[i-1][j]
    print(dp[N][W])
    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
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]"
    v = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)

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

import sys
import numpy as np

#from fractions import gcd

sys.setrecursionlimit(10 ** 9)

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

K = int(input())

ans = 0
M = np.zeros(K+1, dtype=int)
for i in range(1,K+1):
    for j in range(1,K+1):
        M[j] =  gcd(i,j)
        
        for k in range(1,K+1):
            ans += gcd(M[j],k)
#            ans += gcd(gcd(i,j),k)

print(ans)

### FIXED CODE ###

import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)

K = int(input())
mod = 10**9 + 7

N = 3

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

ans = 0

M = np.zeros(K+1, dtype=int)

for i in range(K, 0, -1):
#    print(i)
    M[i] += pow(K//i, N)
    
    for j in range(2,K//i+1):
        j *= i
        M[i] -= M[j]
    
    ans += M[i] * i
    
        
print(ans)
### BUGGY CODE ###

import numpy as np
n = int(input())
a = np.array([int(i) for i in input().split()])
q = int(input())
S = []

for i in range(q):
    b, c = [int(i) for i in input().split()]
    a = np.where(a == b, c, a)
    S.append(np.sum(a))
    
for i in range(q):
    print(S[i])

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
q = int(input())
hako = [0]*(10**6)
ind = list(range(10**6))
S = sum(a)
s = []

for i in a:
    hako[i] += 1

for i in range(q):
    b, c = [int(i) for i in input().split()]
    S += (ind[c] - ind[b])*hako[b]
    s.append(S)
    hako[c] += hako[b]
    hako[b] = 0
for i in range(q):
    print(s[i])
### BUGGY CODE ###

N = int(input())
A = [0]
for i in range(N):
    a = int(input())
    A.append(a)
ans = 1
now = A[1]
while now != 1 and now != 2:
    ans += 1
    now = A[now]
if now == 1:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

N = int(input())
A = [0]
for i in range(N):
    a = int(input())
    A.append(a)
#print(A)
ans = 1
now = A[1]
visited = {}
while (not now in visited) and now != 2:
    ans += 1
    visited[now] = 1
    now = A[now]
#print(visited)
if now != 2:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10**7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


N = in_n()
A = in_nl()

n1, n2, n3 = 0, 0, 0
for i in range(N):
    if A[i] == 1:
        n1 += 1
    elif A[i] == 2:
        n2 += 1
    elif A[i] == 3:
        n3 += 1

dp = [[[-1.0 for _ in range(N + 1)] for _ in range(N + 1)] for _ in range(N + 1)]


def solve(n1, n2, n3):

    if dp[n1][n2][n3] >= 0.0:
        return dp[n1][n2][n3]
    if n1 == n2 == n3 == 0:
        return 0.0

    cnt = n1 + n2 + n3
    ret = 0
    if n3 >= 1:
        ret += solve(n1, n2 + 1, n3 - 1) * n3
    if n2 >= 1:
        ret += solve(n1 + 1, n2 - 1, n3) * n2
    if n1 >= 1:
        ret += solve(n1 - 1, n2, n3) * n1

    ret = (ret + N) / cnt
    dp[n1][n2][n3] = ret
    return ret


print(solve(n1, n2, n3))


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
num1,num2,num3=0,0,0
for i in range(n):
    if a[i]==1:
        num1+=1
    elif a[i]==2:
        num2+=1
    else:
        num3+=1
dp=[[[-1.0 for k in range(n+1)] for i in range(n+1)] for j in range(n+1)]
def f(n1,n2,n3):
    if dp[n1][n2][n3]>=0.0:
        return dp[n1][n2][n3]
    if n1==n2==n3==0:
        return 0.0
    ret=n
    if n1>0:
        ret+=f(n1-1,n2,n3)*n1
    if n2>0:
        ret+=f(n1+1,n2-1,n3)*n2
    if n3>0:
        ret+=f(n1,n2+1,n3-1)*n3
    ret*=1.0/(n1+n2+n3)
    dp[n1][n2][n3]=ret
    return dp[n1][n2][n3]
print(f(num1,num2,num3))
### BUGGY CODE ###

from sys import stdin,stdout


def convert(x):
    if x == 'R': return 0
    if x == 'G': return 1
    if x == 'B': return 2
    

def solve(S,N):
    presum = [[0 for _ in range(3)] for _ in range(N + 1)]
    
    for i in range(N):
        for j in range(3): 
            presum[i + 1][j] += presum[i][j]
        presum[i + 1][S[i]] += 1

    #Exclusion 

    
    sumall = 0
    for i in range(N - 2):
        for k in range(i + 2,N):
            if S[i] != S[k]:
                c = 3 - S[i] - S[k] 
                sumall += presum[k][c] - presum[i + 1][c]
                
                if (i + k) % 2 == 0:
                    j = (i + k)//2
                    if S[j] == c: sumall -= 1
    return sumall


if __name__ == "__main__": 
    #Input 
    N = int(stdin.readline().rstrip())
    S = stdin.readline().rstrip()
    S = [convert(x) for x in S]
    
    print(solve(S,N))
    





### FIXED CODE ###

from sys import stdin,stdout


def solve(S,N):
    color = [[] for _ in range(3)]

    for i in range(N):
        if S[i] == 'R': color[0].append(i)
        elif S[i] == 'G': color[1].append(i)
        else: color[2].append(i)
    
    
    #Exclusion 
    total = len(color[0])*len(color[1])*len(color[2])

    remain = 0
    for i in range(N - 2):
        for j in range(i + 1,N - 1):
            k = j + j - i
            if k >= N: break
            
            if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
                remain += 1
    return total - remain


    


if __name__ == "__main__": 
    #Input 
    N = int(stdin.readline().rstrip())
    S = stdin.readline().rstrip()
    stdout.write(str(solve(S,N)))
### BUGGY CODE ###

N = int(input())
A = list(int(i) for i in input().split())
A.insert(0, 0)
A.append(0)
Q = 0
j=0

for i in range(N):
    while j < N + 1:
        if j == i:
            Q += abs(A[j] - A[j+2])
            j += 1
        else:
            Q += abs(A[j] - A[j+1])
        j += 1
    print("%d" % (Q))
    Q = 0
    j = 0

### FIXED CODE ###

N = int(input())
A = list(int(i) for i in input().split())
A.insert(0, 0)
A.append(0)

Sum = 0
Ans = 0

for i in range(len(A) - 1):
    Sum += abs(A[i+1] - A[i])

for i in range(N):
    Ans = Sum
    Ans = Ans - abs(A[i+1] - A[i]) - abs(A[i+2] - A[i+1]) + abs(A[i+2] - A[i])
    print("%d" % (Ans))
### BUGGY CODE ###

#https://qiita.com/drken/items/dc53c683d6de8aeacf5a(DP問題集)
#https://atcoder.jp/contests/dp/tasks/dp_b
#ボトムアップ的
N, K = list(map(int,input().split()))
h = list(map(int,input().split()))
dp = [float("inf")]*N
dp[0] = 0
dp[1] = abs(h[1]-h[0])

for i in range(2,N,1):
    dp[i] = min([dp[i-j] + abs(h[i] - h[i-j]) for j in range(1,min(i+1,K+1))])

print(dp[N-1])

### FIXED CODE ###

#https://qiita.com/drken/items/dc53c683d6de8aeacf5a(DP問題集)
#https://atcoder.jp/contests/dp/tasks/dp_b
#ボトムアップ的
N, K = list(map(int,input().split()))
h = list(map(int,input().split()))
dp = [float("inf")]*N
dp[0] = 0
dp[1] = abs(h[1]-h[0])

for i in range(2,N,1):
    dp[i] = min([dp[i-j] + abs(h[i] - h[i-j]) for j in range(1,min(i+1,K+1))])

print(dp[N-1])
### BUGGY CODE ###

n = int(input())
a = list(input().split())
check = 10**18
ans = int(a[0])
tmp = 0
for  i in range(1,n):
    if '0' in a:
        ans = 0
        break
    ans = ans * int(a[i])
    if ans > check:
        tmp = 1
        break

if tmp == 0:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
check = 10**18

a = sorted(a)
ans = a[0]
tmp = 0


for i in range(n-1,0,-1):
    ans = ans * a[i]
    if ans > check:
        tmp  = 1
        break
    elif a[0] == 0:
        tmp = 2
        break

if tmp == 1:
    print('-1')
elif tmp == 0:
    print(ans)
elif tmp == 2:
    print('0')
### BUGGY CODE ###

a,b=map(int,input().split())

amari=[(a*(a+1)%2019)]
for i in range(a,b):
    for j in range(i+1,b+1):
        if (i*j)%2019<amari[-1]:
            amari.append((i*j)%2019)

print(amari[-1])

### FIXED CODE ###

a,b=map(int,input().split())


amari=[(a*(a+1)%2019)]
for i in range(a,b):
    for j in range(i+1,b+1):
        x=i%2019
        y=j%2019
        if x==0 or y==0:
            print(0)
            exit()
        elif (x*y)%2019<amari[-1]:
            amari.append((x*y)%2019)

print(amari[-1])