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

import sys
input = sys.stdin.buffer.readline

def main():
    N,K = map(int,input().split())
    a = list(map(int,input().split()))
    f = list(map(int,input().split()))
    a.sort()
    f.sort(reverse = True)
    l,r = -1,a[-1]*f[0]+1
    while r-l > 1:
        mid = (l+r)//2
        count = 0
        for i in range(N):
            tr = max(0,a[i] - mid//f[i])
            count += tr
        if K < count:
            l = mid
        else:
            r = mid
            
    print(r)
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
import numpy as np

def main():
    N,K = map(int,input().split())
    a = list(map(int,input().split()))
    f = list(map(int,input().split()))
    a.sort()
    f.sort(reverse=True)

    if sum(a) <= K:
        print(0)
    else:
        a = np.array(a)
        f = np.array(f)
        left,right = 0,max(a)*max(f)
        while right-left > 1:
            mid = (left+right)//2
            pra = a-mid//f
            pra[pra<0] = 0
            if np.sum(pra) > K:
                left = mid
            else:
                right = mid
        print(right)

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

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


def comdiv(n, m):
    cds = []  # exclude 1
    for i in range(2, min(n, m) + 1):
        if n % i == 0 and m % i == 0:
            cds.append(i)

    return sorted(cds)


def main(a, b):
    cds = comdiv(a, b)
    cand = set()

    for cd in cds:
        if len(cand) == 0:
            cand.add(cd)
            continue
        if all([cd % x != 0 for x in cand]):
            cand.add(cd)

    return len(cand) + 1


print(main(a, b))

### FIXED CODE ###

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


def prime_factorize(n):
    """Return the prime factorization of n > 1.
    >>> prime_factorize(36)
    [2, 2, 3, 3]
    """
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2

    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2

    if n != 1:
        a.append(n)

    return a


def main(a, b):
    pf_a = set(prime_factorize(a))
    pf_b = set(prime_factorize(b))
    return len(pf_a & pf_b) + 1


print(main(a, b))
### BUGGY CODE ###

a,b=map(int ,input().split())
x=int(pow(b,1/a))
x+=1
while x>=1:
    if b%(x**a)==0:
        print(x)
        exit()
    x-=1



### FIXED CODE ###

a,b=map(int ,input().split())
x=int(pow(b,1/a)+0.00001)
while x>=1:
    if b%(x**a)==0:
        print(x)
        exit()
    x-=1
### BUGGY CODE ###

import math
K = int(input())
ans = 0
for i in range(K):
  i += 1
  for j in range(K):
    j += 1
    for k in range(K):
      k += 1
      ans += math.gcd(math.gcd(i, j), k)
print(ans)


### FIXED CODE ###

import numpy as np

K = int(input())
r = np.arange(1, K + 1)
print(np.sum(np.gcd.outer(np.gcd.outer(r, r), r)))
### BUGGY CODE ###

from collections import deque
H,W = map(int,input().split())
maze = []
for i in range(H):
    maze.append(input())
q = deque()
saitan = [1000000]*H*W
for i in range(H):
    for k in range(W):
        if maze[i][k] == '#':
            q.append(i*W+k)
            saitan[i*W+k] = 0

#print(start)
def bfs(h,w,q,Saitan):
    
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    while len(q)>0 and (1000000 in saitan):
        j = q.popleft()
        y = int(j/w)
        x = j%w
        #print(saitan)
        for k in range(4):
            my = y + dy[k]
            mx = x + dx[k]
            #print(sx,sy,j,x,y,mx,my)
            if not((0 <=my <= h-1) and (0 <= mx <= w-1)):
                #print('q')
                continue
            if saitan[(my*w + mx)] <= saitan[y*w + x] + 1:
                #print('c')
                continue
                
            saitan[(my*w + mx)] = saitan[y*w + x] + 1
            q.append(my*w + mx)
            #Sumi.append(my*w + mx)
    return max(saitan)

print(bfs(H,W,q,saitan))
#print(saitan)

### FIXED CODE ###

from collections import deque
H,W = map(int,input().split())
maze = []
for i in range(H):
    maze.append(input())
q = deque()
saitan = [1000000]*H*W
for i in range(H):
    for k in range(W):
        if maze[i][k] == '#':
            q.append(i*W+k)
            saitan[i*W+k] = 0
len_q = len(q)

#print(start)
def bfs(h,w,q,Saitan,len_Q):
    
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    while len(q)>0 and len_Q < h * w:
        j = q.popleft()
        y = int(j/w)
        x = j%w
        #print(saitan)
        for k in range(4):
            my = y + dy[k]
            mx = x + dx[k]
            #print(sx,sy,j,x,y,mx,my)
            if not((0 <=my <= h-1) and (0 <= mx <= w-1)):
                #print('q')
                continue
            if saitan[(my*w + mx)] <= saitan[y*w + x] + 1:
                #print('c')
                continue
                
            saitan[(my*w + mx)] = saitan[y*w + x] + 1
            q.append(my*w + mx)
            len_Q += 1
            #Sumi.append(my*w + mx)
    return max(saitan)

print(bfs(H,W,q,saitan,len_q))
#print(saitan)
### BUGGY CODE ###

N , K = map(int, input().split())
p = list(map(int, input().split()))
Etop = 0
E = 0
q = []
for j in p:
    q.append((j+1) / 2)

for i in range(N-K+1):
    E = 0
    for n in range(K):
        E += q[n+i]
    if E > Etop:
        Etop = E
print(Etop)

### FIXED CODE ###

N , K = map(int, input().split())
p = list(map(int, input().split()))
Etop = 0
E = 0
q = []
Ruiseki = 0
S = []
Top = 0
for i in p:
    q.append((i+1) / 2)

for E in q:
    Ruiseki += E
    S.append(Ruiseki)

if N == K:
    print(S[N-1])
    quit()
else:
    for j in range(N-K):
        Sig = S[K+j] - S[j]
        if Sig > Top:
            Top = Sig

print(Top)
### BUGGY CODE ###

import itertools

n = int(input())
s = list(input())
l = list(itertools.combinations(s,3))
c = []
for i in l:
  if not i in c:
    c.append(i)

print(len(c))

### FIXED CODE ###

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

count = 0

for i in range(1000):
  a = "{0:03d}".format(i)
  if a[0] in s:
    idx1 = s.index(a[0])
    s1 = s[idx1+1:]
    if a[1] in s1:
      idx2 = s1.index(a[1])
      s2 = s1[idx2+1:]
      if a[2] in s2:
        count += 1
print(count)
### BUGGY CODE ###

import math

N, K = map(int, input().split())
h = [0] + list(map(int, input().split()))

DP = [math.inf] * (N+1)

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


print(DP[N])



### FIXED CODE ###

import math

N, K = map(int, input().split())
h = [0] + list(map(int, input().split()))

DP = [math.inf] * (N+1)

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


print(DP[N])
### BUGGY CODE ###

import sys
input = sys.stdin.readline


Q = int(input())
Query = []
for _ in range(Q):
    N = int(input())
    A = list(map(int, input().split()))
    S = input().rstrip()
    Query.append((N, A, S))

def solve(N, A, S):
    Now = {0}
    for i in reversed(range(N)):
        s = S[i]
        a = A[i]
        if s == "0":
            New = set()
            for s in Now:
                New.add(s)
                New.add(s^a)
            Now = New
        else:
            if not a in Now:
                return False
    return True

for N, A, S in Query:
    print(0 if solve(N, A, S) else 1)

### FIXED CODE ###

import sys
input = sys.stdin.readline


Q = int(input())
Query = []
for _ in range(Q):
    N = int(input())
    A = list(map(int, input().split()))
    S = input().rstrip()
    Query.append((N, A, S))



def solve(N, A, S):
    Base = []
    for i in reversed(range(N)):
        s = S[i]
        a = A[i]
        if s == "0":
            for b in Base:
                a = min(a, a^b)
            if a:
                Base.append(a)
        else:
            for b in Base:
                a = min(a, a^b)
            if a:
                return False
                
    return True

for N, A, S in Query:
    print(0 if solve(N, A, S) else 1)
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,k = LI()
    a = LI()
    r = [0] * n
    for i in range(1,n):
        t = inf
        for j in range(1,min(i, k)+1):
            u = r[i-j] + abs(a[i-j]-a[i])
            if t > u:
                t = u
        r[i] = t

    return r[-1]


print(main())


### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,k = LI()
    a = LI()
    r = [0] * n
    for i in range(1,n):
        ai = a[i]
        t = r[i-1] + abs(a[i-1]-ai)
        mj = i - k
        if mj < 0:
            mj = 0
        for j in range(mj,i-1):
            u = r[j] + abs(a[j]-ai)
            if t > u:
                t = u

        r[i] = t

    return r[-1]


print(main())
### BUGGY CODE ###

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

ans = [0] * n
for i in range(len(a) - 1):
    if ans[i] == 1:
        continue
    for j in range(i + 1, len(a)):
        if a[i] % a[j] == 0:
            ans[i] = 1
        if a[j] % a[i] == 0:
            ans[j] = 1
print(n - sum(ans))

### FIXED CODE ###

def main():
    n = int(input())
    a = tuple(map(int, input().split()))

    ans = 0
    mx = max(a) + 1
    dp = [0] * mx
    for i in a:
        for j in range(i, mx, i):
            dp[j] += 1
    for i in a:
        if dp[i] == 1:
            ans += 1

    print(ans)


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

A,B,K = map(int,input().split())
ansnums =[i for i in range(B-K+1,B+1)]
nums = [i for j,i in enumerate(range(A,B+1)) if j<K or i in ansnums]
anss = sorted(set(nums))
for i in anss:
    print(i)

### FIXED CODE ###

A,B,K = map(int,input().split())
ansnums = [A+k for k in range(K) if A+K<=B]
ansnums.extend([B-k for k in range(K) if B-k>=A])
ansnums = sorted(set(ansnums))
for i in ansnums:
    print(i)
### BUGGY CODE ###

s=input()
q=int(input())
dir=True
ans=s
query=[]
for i in range(q):
  temp=input()
  if temp[0] == "1":
    dir = dir ^ True
  if temp[0] == "2":
    t,f,c = temp.split()

    if (f == "1" and dir) or (f=="2" and not dir):
      ans=c+ans
    else:
      ans=ans+c
def reverse(s):
  t=""
  for i in range(len(s)-1,-1,-1):
    t+=s[i]
  return t

if dir:
  print(ans)
else:
  print(reverse(ans))


### FIXED CODE ###

s=input()
q=int(input())
dir=True
ans=s
right=""
left=""
query=[]
for i in range(q):
  temp=input()
  if temp[0] == "1":
    dir = dir ^ True
  if temp[0] == "2":
    t,f,c = temp.split()

    if (f == "1" and dir) or (f=="2" and not dir):
      left=c+left
    else:
      right=right+c

def reverse(s):
  t=""
  for i in range(len(s)-1,-1,-1):
    t+=s[i]
  return t

if dir:
  print(left+ans+right)
else:
  t=reverse(right)+reverse(ans)+reverse(left)
  print(t)
### BUGGY CODE ###

import sys
import re
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


def main():
    S = input()

    ans = 0
    res = re.findall(r'A*ABC(?:A|BC)*', S)
    for r in res:
        r = re.sub(r'(BC)', 'X', r)
        cnt = 0
        for c in r[::-1]:
            if c == 'X':
                cnt += 1
            else:
                ans += cnt

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import re
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


# def main():
#     S = input()

#     ans = 0
#     res = re.findall(r'A*ABC(?:A|BC)*', S)
#     for r in res:
#         r = re.sub(r'(BC)', 'X', r)
#         cnt = 0
#         for c in r[::-1]:
#             if c == 'X':
#                 cnt += 1
#             else:
#                 ans += cnt

#     print(ans)


def main():
    S = input()

    S = re.sub(r'(BC)', 'X', S)

    ans = 0
    cnt = 0
    for s in S[::-1]:
        if s == 'X':
            cnt += 1
        elif s == 'A':
            ans += cnt
        else:
            cnt = 0

    print(ans)


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

# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

H,W,K=map(int,input().split())
sy,sx,gy,gx=map(int,input().split())
st=sx+sy*(W+2)
gl=gx+gy*(W+2)
c=['@']*(W+2)
for i in range(H):
    c.extend(['@']+list(input())+['@'])
c.extend(['@']*(W+2))
que=deque()
dist=[INF]*(W+2)*(H+2)
que.append(st)
dist[st]=0
d=(-1,1,W+2,-(W+2))
while que:
    v=que.popleft()
    tmp_dist=dist[v]
    for k in range(4):
        nv=v
        for _ in range(K):
            nv+=+d[k]
            if c[nv]=='.' and dist[nv]>tmp_dist:
                    dist[nv]=tmp_dist+1
                    que.append(nv)
            else:
                break
print(dist[gl] if dist[gl]!=INF else -1)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

H,W,K=map(int,input().split())
sy,sx,gy,gx=map(int,input().split())
st=sx+sy*(W+2)
gl=gx+gy*(W+2)
c=['@']*(W+2)
for i in range(H):
    c.extend(['@']+list(input())+['@'])
c.extend(['@']*(W+2))
que=deque()
dist=[INF]*(W+2)*(H+2)
que.append(st)
dist[st]=0
d=(-1,1,W+2,-(W+2))
while que:
    v=que.popleft()
    for k in range(4):
        nv=v
        for _ in range(K):
            nv+=+d[k]
            if c[nv]=='.' and dist[nv]>dist[v]:
                if dist[nv]==INF:
                    dist[nv]=dist[v]+1
                    que.append(nv)
            else:
                break
print(dist[gl] if dist[gl]!=INF else -1)
### BUGGY CODE ###

n, m = list(map(int, input().split()))
d = m//n+1
for x in range(d)[::-1]:
  if m%x==0:
    break
print(x)

### FIXED CODE ###

N, M = list(map(int, input().split(" ")))
def solv(N, M):
    d = M//N
    for i in range(d+1)[::-1]:
        if M%i == 0:
            return i
print(solv(N, M))
### BUGGY CODE ###

N = int(input())
S = input()
lst = []
for i in range(N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            lst.append(S[i]+S[j]+S[k])
print(len(set(lst)))

### FIXED CODE ###

N = int(input())
S = input()
lst = []
count = 0
for i in range(1000):
    num = str(i).zfill(3)
    if num[0] in S:
        a1 = S.index(num[0])
        if num[1] in S[a1+1:]:
            a2 = S[a1+1:].index(num[1]) + a1+1
            if num[2] in S[a2+1:]:
                count += 1
print(count)
### BUGGY CODE ###

x,y,z,k = map(int,input().split())
lia = sorted(list(map(int,input().split())))
lib = sorted(list(map(int,input().split())))
lic = sorted(list(map(int,input().split())))

li2 = sorted(list(a+b for a in lia for b in lib),reverse = True)[:k]
li3 = sorted(list(ab + c for ab in li2 for c in lic),reverse = True)

for i in range(k):
    print(li3[i])


### FIXED CODE ###

def main():
    x,y,z,k = map(int,input().split())
    lia = sorted(list(map(int,input().split())))
    lib = sorted(list(map(int,input().split())))
    lic = sorted(list(map(int,input().split())))

    li2 = sorted(list(a+b for a in lia for b in lib),reverse = True)[:k]
    li3 = sorted(list(ab + c for ab in li2 for c in lic),reverse = True)[:k]

    print('\n'.join(map(str,li3)))

main()
### BUGGY CODE ###

def main():
    N = int(input())
    A_list = list(map(int, input().split()))

    ans = 1
    for i in A_list:
        ans *= i
        if 1000000000000000000 < ans and 0 not in set(A_list):
            print('-1')
            exit()
        elif ans == 0:
            print(0)
            exit()
    else:
        print(ans)


main()

### FIXED CODE ###

def main():
    N = int(input())
    A_list = list(map(int, input().split()))

    if 0 in set(A_list):
        print(0)
        exit()

    ans = 1
    for i in A_list:
        ans *= i
        if 1000000000000000000 < ans:
            print('-1')
            exit()
    else:
        print(ans)


main()
### BUGGY CODE ###

import sys
X = int(input())
for i in range(1,int(X**(0.5)+1)):
    if X % i ==0:
        a=0
        b=-i
        while a**5<X**5:
            a+=1
            b+=1
            if a**5-b**5==X:
                print(a,b)
                sys.exit()

### FIXED CODE ###

import sys
X = int(input())
for i in range(1,int(X**(0.5)+1)):
    if X % i ==0:
        a=0
        b=-i
        while a**5<X**2:
            a+=1
            b+=1
            if a**5-b**5==X:
                print(a,b)
                sys.exit()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
D = {0:0,1:0,2:0,3:0}
for a in A :
    D[a] += 1

dp = [[[0]*(N+1) for j in range(N+1)] for i in range(N+1)]

def f(c1, c2, c3) :
    res = N
    if (c1 > 0) :
        res += dp[c1-1][c2][c3] * c1
    if (c2 > 0) :
        res += dp[c1+1][c2-1][c3] * c2
    if (c3 > 0) :
        res += dp[c1][c2+1][c3-1] * c3
    
    res /= (c1 + c2 + c3)
    dp[c1][c2][c3] = res

for k in range(D[3]+1) :
    for j in range(D[2]+D[3]+1 - k) :
        for i in range(D[1]+D[2]+D[3]+1 - (j+k)) :
            if i+j+k == 0 :
                continue
            f(i, j, k)

ans = dp[D[1]][D[2]][D[3]]

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
D = {0:0,1:0,2:0,3:0}
for a in A :
    D[a] += 1

one = D[1]
two = D[2]
three = D[3]

dp = [[[0.0]*(N+1) for j in range(N+1)] for i in range(N+1)]

def f(c1, c2, c3) :
    res = N
    if (c1 > 0) :
        res += dp[c1-1][c2][c3] * c1
    if (c2 > 0) :
        res += dp[c1+1][c2-1][c3] * c2
    if (c3 > 0) :
        res += dp[c1][c2+1][c3-1] * c3
    
    dp[c1][c2][c3] = res/(c1 + c2 + c3)

for k in range(three+1) :
    for j in range(two+three+1 - k) :
        for i in range(one+two+three+1 - (j+k)) :
            if i+j+k == 0 :
                continue
            f(i, j, k)

print(dp[one][two][three])
### BUGGY CODE ###

n = int(input())
d = {}

for _ in range(n):
  s = input()
  if s not in d:
    d[s] = 1
  else:
    d[s] += 1

max_k_list = [kv[0] for kv in d.items() if kv[1] == max(d.values())]

for i in sorted(max_k_list):
  print(i)


### FIXED CODE ###

n = int(input())
d = {}

for _ in range(n):
  s = input()
  d[s] = d.get(s, 0) + 1 

n = max(d.values())
max_k_list = [kv[0] for kv in d.items() if kv[1] == n]
max_k_list.sort()

for i in max_k_list:
  print(i)
### BUGGY CODE ###

def main():
  S=input()
  N=int(input())
  cnt=0
  for i in range(N):
    tmp=[i for i in input().split() ]
    if tmp[0]=='1':
      cnt+=1
    else:
      if (cnt+int(tmp[1]))%2==1:
        new=tmp[2]+S
        S=new
      else:
        new=S+tmp[2]
        S=new
  if cnt%2!=0:
    S=''.join(list(reversed(S)))

  print(S)
if __name__=='__main__':
  main()
   


### FIXED CODE ###

def main():
  S=input()
  N=int(input())
  cnt=0
  f=''
  b=''
  for i in range(N):
    tmp=[i for i in input().split() ]
    if tmp[0]=='1':
      cnt+=1
    else:
      if (cnt+int(tmp[1]))%2==1:
        f=tmp[2]+f
        
      else:
        b=b+tmp[2]
  ans=f+S+b        
  if cnt%2!=0:
    ans=''.join(list(reversed(ans)))

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

import numpy as np
n = int(input())
a = list(map(int, input().split()))
b = np.zeros(n-1)
for i in range(1,n):
    b[i-1] = a.count(i)
b = np.append(b,0)
for i in b:
    print(int(i))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))

d = {}

for i in range(N - 1):
    if A[i] in d:
        d[A[i]].append(i + 2)
    else:
        d[A[i]] = [i + 2]

for i in range(1, N + 1):
    if i in d:
        print(len(d[i]))
    else:
        print(0)
### BUGGY CODE ###

# coding: utf-8
import itertools
import math
N = int(input())
S = list(input())

R = [0]*N
G = [0]*N
B = [0]*N

for i in range(N):
    if S[i] == 'R':
        R[i] += 1
    elif S[i] == 'G':
        G[i] += 1
    else:
        B[i] += 1

for i in range(N-1):
    R[i+1] += R[i]
    G[i+1] += G[i]
    B[i+1] += B[i]
ans = 0
#print(R,G,B)
for i in range(N-2):
    for j in range(i+1,N-1):
        if len(set([S[i],S[j]])) == 2:
            s = list(set(['R','G','B']) ^ set([S[i],S[j]]))[0]
            if s == 'R':
                ans += R[N-1] - R[j]
                if 2*j-i<=N-1 and S[2*j-i] == 'R':
                    ans -= 1
            if s == 'G':
                ans += G[N-1] - G[j]
                if 2*j-i <= N-1 and S[j+j-i] == 'G':
                    ans -= 1
            if s == 'B':
                ans += B[N-1] - B[j]
                if 2*j-i <= N-1 and S[j+j-i] == 'B':
                    ans -= 1
print(ans)


### FIXED CODE ###

# coding: utf-8
import itertools
import math
import sys
#input→sys.stdin.readline半分の時間に
input=sys.stdin.readline
N = int(input())
S = list(input())

R = [0]*N
G = [0]*N
B = [0]*N

for i in range(N):
    if S[i] == 'R':
        R[i] += 1
    elif S[i] == 'G':
        G[i] += 1
    else:
        B[i] += 1

for i in range(N-1):
    R[i+1] += R[i]
    G[i+1] += G[i]
    B[i+1] += B[i]
ans = 0
#print(R,G,B)
for i in range(N-2):
    for j in range(i+1,N-1):
        if len(set([S[i],S[j]])) == 2:
            s = list(set(['R','G','B']) ^ set([S[i],S[j]]))[0]
            if s == 'R':
                ans += R[N-1] - R[j]
                if 2*j-i<=N-1 and S[2*j-i] == 'R':
                    ans -= 1
            if s == 'G':
                ans += G[N-1] - G[j]
                if 2*j-i <= N-1 and S[j+j-i] == 'G':
                    ans -= 1
            if s == 'B':
                ans += B[N-1] - B[j]
                if 2*j-i <= N-1 and S[j+j-i] == 'B':
                    ans -= 1
print(ans)
### BUGGY CODE ###

N = int(input())
A = sorted(map(int, input().split()))

count = N
for i in range(N - 1, -1, -1):
    if sum(A[0:i]) * 2 >= A[i]:
        continue

    else:
        if (i == 0):
            continue
        count -= len(A[0:i])
        break

print(count)


### FIXED CODE ###

N = int(input())
A = sorted(map(int, input().split()))
sum_A = sum(A)
count = N
for i in range(N - 1, -1, -1):
    sum_A -= A[i]
    if (sum_A) * 2 >= A[i]:
        continue

    else:
        if (i == 0):
            continue
        count -= len(A[0:i])
        break

print(count)