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

s=input()
N=len(s)
t=input()
M=len(t)

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']

index={moji:[] for moji in alphabetlist}
for i in range(N):
    index[s[i]].append(i)

dp=[[[] for i in range(0,N)] for j in range(0,M)]

for i in range(0,N):
    if index[t[0]]:
        if i>=index[t[0]][0]:
            dp[0][i]=[t[0]]

for i in range(0,M):
    for j in range(0,N):
        x=t[i]
        if index[x] and j>=index[x][0]:
            start=0
            end=len(index[x])-1
            while end-start>1:
                test=(end+start)//2
                if j>=index[x][test]:
                    start=test
                else:
                    end=test
            if j>=index[x][end]:
                next=index[x][end]-1
            else:
                next=index[x][start]-1
            if next>=0:
                if len(dp[i-1][j])>1+len(dp[i-1][next]):
                    dp[i][j]=dp[i-1][j]
                else:
                    dp[i][j]=dp[i-1][next]+[t[i]]
            else:
                if dp[i-1][j]==[]:
                    dp[i][j]=[t[i]]
                else:
                    dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=dp[i-1][j]

print(''.join(dp[M-1][N-1]))

### FIXED CODE ###

s=input()
N=len(s)
t=input()
M=len(t)

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
def al(str):
    return alphabetlist.index(str)+1

dp=[[0 for i in range(0,M+1)] for i in range(0,N+1)]

for i in range(0,N):
    for j in range(0,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]

ans=[]
i=N
j=M
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans.append(s[i-1])
        i-=1
        j-=1

ans=ans[::-1]
print(''.join(ans))
### BUGGY CODE ###

S=input()
N=len(S)

T=[0]
for i in range(N):
    p = int(S[-1-i])
    T.append( (T[-1]+(p*(10**i))%2019)%2019 )
    
from collections import Counter
ans=0
U=dict(Counter(T))
for num in U:
    ans += U[num]*(U[num]-1)//2
print(ans)

### FIXED CODE ###

S=input()
N=len(S)

T=[0]
for i in range(N):
    p = int(S[-1-i])
    T.append( (T[-1]+ pow(10,i,2019)*p)%2019 )
    
from collections import Counter
ans=0
U=dict(Counter(T))
for num in U:
    ans += U[num]*(U[num]-1)//2
print(ans)
### BUGGY CODE ###

n = int(input())

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

def mul3(n):
    return n*3

count = 0
while any([a[i] % 2 == 0 for i in range(n)]):
    a = list(map(mul3, a))
    for i in range(n):
        if a[i] % 2 == 0:
            a[i] //= 6
            break
    count += 1
print(count)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
c=0
for i in a:
    while i%2==0:i,c=i/2,c+1
print(c)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = abs(a[0]-a[-1])
for i in range(1,n):
  sumu = a[0:i]
  arai = a[i:]
  kari = abs(sum(sumu)-sum(arai))
  if kari < ans:
    ans = kari
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
max_ans = sum(a)
ans = abs(a[0]-(max_ans - a[0]))
sumu = a[0]
for i in range(1,n-1):
  sumu += a[i]
  arai = max_ans - sumu
  kari = abs(sumu-arai)
  if kari < ans:
    ans = kari
print(ans)
### BUGGY CODE ###

import numpy as np
import collections
deque=collections.deque
H,W=map(int,input().split())
A=[list(input()) for j in range(H)]
went=[[False]*W for i in range(H)]
queue=deque()
for x,i in enumerate(A):
    for y,j in enumerate(i):
        if j=="#":
            went[x][y]=True
            queue.append((x,y,0))
while queue:
    curx,cury,ct=queue.popleft()
    for dx,dy in ((1,0),(-1,0),(0,1),(0,-1)):
        newx,newy=curx+dx,cury+dy
        newct=ct+1
        if 0<=newx<H and 0<=newy<W and (not went[newx][newy]):
            went[newx][newy]=True
            queue.append((newx,newy,newct))
print(ct)

### FIXED CODE ###

import collections
H,W=map(int,input().split())
went=[[False]*W for i in range(H)]
queue=collections.deque()
for hoge in range(H):
    for huga,t in enumerate(input()):
        if t=="#":
            went[hoge][huga]=True
            queue.append([hoge,huga,0])
while queue:
    curx,cury,ct=queue.popleft()
    for dx,dy in [[1,0],[-1,0],[0,1],[0,-1]]:
        newx,newy=curx+dx,cury+dy
        newct=ct+1
        if 0<=newx<H and 0<=newy<W and (not went[newx][newy]):
            went[newx][newy]=True
            queue.append([newx,newy,newct])
print(ct)
### BUGGY CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [1e+10 for i in range(n)]
dp[0] = 0

for i in range(0,n):
    for j in range(1,k+1):
        p = i + j
        if p < n:
            dp[p] = min(dp[p],dp[i] + abs(h[i] - h[p]))
print(dp[n-1])

### FIXED CODE ###


INF = 2**31-1
n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [INF for _ in range(n)]

dp[0] = 0

for i in range(0,n):
    for j in range(1,k+1):
        if i+j < n:
            dp[i+j] = min(dp[i+j], abs(h[i+j] - h[i]) + dp[i])
        else: break

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

n = int(input())
 
def q(l, r, t):
    m = (l + r + 1) // 2
    print(m) ; rm = input()[0]
    if (m - b)%2 == (rm != t):
        q(m, r, rm)
    else:
        q(l, m-1, t)
 
print(0)
q(0, n-1, input()[0])

### FIXED CODE ###

n = int(input())
q = lambda i:input('%d\n'%i)
i, j = 0, n - 1
a, b = q(i), q(j)
while True:
  k = (j - i + 1) // 2 + i
  c = q(k)
  if (k - i)%2 == (a==c):
    j = k
  else:
    a = c
    i = k
### BUGGY CODE ###

r,g,b,n=map(int,input().split())
count=0
for ri in range(int(n/r)+1):
    for gi in range(int(n/g)+1):
        sumc=n-ri*r-gi*g
        if sumc<0:
            break
        if sumc%b==0 and sumc/b>=0:
            count+=1
print(count)


### FIXED CODE ###

r,g,b,n=map(int,input().split())

count=0
for ri in range(int(n/r)+1):
    for gi in range(int((n-ri*r)/g)+1):
        sumc=n-ri*r-gi*g
        if sumc<0:
            break
        if sumc%b==0:
            count+=1

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

import bisect
import math
n = int(input())
l = sorted(list(map(int,input().split())))
a = l[-1]/2
s = bisect.bisect_left(l,a)
k1 = l[s]
if len(l)==2 and l[0]==0:
  print(l[-1],0)
  exit()
k2 = l[s+1]
def com(a,b):
  return math.factorial(a)//(math.factorial(b)*math.factorial(a-b))

s1 = com(l[-1],k1)
s2 = com(l[-1],k2)
if s1>=s2:
  print(l[-1],k1)
else:
  print(l[-1],k2)

### FIXED CODE ###

import bisect
import math
n = int(input())
l = sorted(list(map(int,input().split())))
if len(l)==2 :
  print(l[-1],l[-2])
  exit()
  
a = l[-1]/2
s = bisect.bisect_left(l,a)
if l[s]==a:
  print(l[-1],l[s])
  exit()
k1 = l[s-1]
k2 = l[s]
s1 = a-k1
if k2==l[-1]:
  k2 = k1
s2 = abs(k2-a)
#print(s,k1,k2,s1,s2)
if s1<=s2:
  print(l[-1],k1)
else:
  print(l[-1],k2)
### BUGGY CODE ###

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

import heapq

Q=[]
for i in range(N):
    Q.append((-L[i],L[i],1))
heapq.heapify(Q)

for i in range(K):
    l,B,cnt=heapq.heappop(Q)
    heapq.heappush(Q,(-B/(cnt+1),B,cnt+1))
#print(Q)
#print(Q[0][0])

import math
ans=-Q[0][0]
print(math.ceil(ans))

### FIXED CODE ###

N,K=map(int,input().split())
L=list(map(int,input().split()))
    
import math
MAX=10**9
MIN=0
for i in range(100):
    Mid=(MAX+MIN)/2
    cnt=0
    for j in range(N):
        cnt+=L[j]//Mid
    if cnt<=K:
        MAX=Mid
    else:
        MIN=Mid
    #print(cnt)
print(math.ceil(Mid))
### BUGGY CODE ###

K, S = map(int, input().split())
c = 0
for x in range(K + 1):
    for y in range(x + 1):
        for z in range(y + 1):
            if x + y + z == S:
                if x != y and x!= z and y!= z:
                    c += 6
                elif x == y and x == z and y == z:
                    c += 1
                else:
                    c += 3
print(c)

### FIXED CODE ###

K, S = map(int, input().split())
c = 0
for x in range(K + 1):
    for y in range(x + 1):
        if x + y > S:
            break
        z = S - x - y
        if z >= 0 and z < y + 1:
            if x != y and x!= z and y!= z:
                c += 6
            elif x == y and x == z and y == z:
                c += 1
            else:
                c += 3
print(c)
### BUGGY CODE ###

N, X, Y = map(int, input().split())
X -= 1
Y -= 1
edge = []
for i in range(N):
    edge.append([])
    if i != 0:
        edge[i].append(i - 1)
    if i != N-1:
        edge[i].append(i + 1)
edge[X].append(Y)
edge[Y].append(X)

answer = [0] * (N - 1)
for i in range(N):
    queue = []
    for e in edge[i]:
        queue.append(e)
    counter = 0
    d = [N + 10] * N
    d[i] = 0
    # i is start
    while counter < len(queue):
        node = queue[counter]
        min_dist = N + 10
        for e in edge[node]:
            min_dist = min(d[e], min_dist)
        d[node] = min_dist + 1
        for e in edge[node]:
            if d[e] == N+10:
                queue.append(e)
        counter += 1
    for i in d:
        answer[i] += 1
for a in answer[1:]:
    print(a//2)
print('0')

### FIXED CODE ###

N, X, Y = map(int, input().split())
X -= 1
Y -= 1
edge = []
for i in range(N):
    edge.append([])
    if i != 0:
        edge[i].append(i - 1)
    if i != N-1:
        edge[i].append(i + 1)
edge[X].append(Y)
edge[Y].append(X)

answer = [0] * (N - 1)
for i in range(N):
    queue = []
    for e in edge[i]:
        queue.append(e)
    counter = 0
    d = [N + 10] * N
    d[i] = 0
    # i is start
    while counter < len(queue):
        node = queue[counter]
        min_dist = N + 10
        for e in edge[node]:
            if d[e] < min_dist:
                min_dist = d[e]
            if d[e] == N + 10:
                queue.append(e)
        d[node] = min_dist + 1
        counter += 1
    for i in d:
        answer[i] += 1
for a in answer[1:]:
    print(a//2)
print('0')
### BUGGY CODE ###

n,p=map(int,input().split())
s=input()

count=0
if p==2:
    for i in range(n):
        if int(s[i])%2==0:
            count+=i+1
elif p==5:
    for i in range(n):
        if int(s[i])%5==0:
            count+=i+1
else:
    unum=[]
    for i in range(p):
        unum.append(0)
    num=0
    for i in range(n):
        unum[int(s[i:n])%p]+=1
    unum[0]+=1
    for i in range(p):
        if unum[i]>=2:
            count+=round((unum[i]*(unum[i]-1))*0.5)
print(count)

### FIXED CODE ###

n,p=map(int,input().split())
s=input()

count=0
if p==2:
    for i in range(n):
        if int(s[i])%2==0:
            count+=i+1
elif p==5:
    for i in range(n):
        if int(s[i])%5==0:
            count+=i+1
else:
    lis=[1]
    for i in range(n-1):
        lis.append((lis[i]*10)%p)
    lis.reverse()
    for i in range(n):
        lis[i]=(int(s[i])*lis[i])%p
    unum=[1]
    for i in range(p-1):
        unum.append(0)
    num=0
    for i in range(n):
        num=(num+lis[n-i-1])%p
        unum[num]+=1
    for i in range(p):
        unumi=unum[i]
        count+=(unumi*(unumi-1))*0.5
print(round(count))
### BUGGY CODE ###

# dp[c1][c2][c3]=
# 		(1個の皿がc1枚、2個の皿がc2枚、3個の皿がc3枚あるとき、全て食べるまでの操作回数の期待値)

N = int(input())
A = list(map(int, input().split()))
cnt1 = A.count(1)
cnt2 = A.count(2)
cnt3 = A.count(3)

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

# dp[c1][c2][c3]=1
# 	+dp[c1−1][c2][c3]∗(1個の皿が選ばれる確率)
# 	+dp[c1+1][c2−1][c3]∗(2個の皿が選ばれる確率)
# 	+dp[c1][c2+1][c3−1]∗(3個の皿が選ばれる確率)
# 	+dp[c1][c2][c3]∗(0個の皿が選ばれる確率)
# ↓式変形↓
# dp[c1][c2][c3]=1/(1−(0個の皿が選ばれる確率))
# 			+ dp[c1−1][c2][c3]*(1個の皿が選ばれる確率)/(1−(0個の皿が選ばれる確率))
# 			+ dp[c1+1][c2−1][c3]*(2個の皿が選ばれる確率)/(1−(0個の皿が選ばれる確率))
# 			+ dp[c1][c2+1][c3−1]*(3個の皿が選ばれる確率)/(1−(0個の皿が選ばれる確率))


def func(c1, c2, c3):
    if dp[c1][c2][c3] != -1:
        return dp[c1][c2][c3]

    temp = 1 / (1 - ((N - c1 - c2 - c3) / N))
    if c1 > 0:
        temp += func(c1 - 1, c2, c3) * (c1 / N) / (1 - (N - c1 - c2 - c3) / N)
    if c2 > 0:
        temp += func(c1 + 1, c2 - 1, c3) * (c2 / N) / \
            (1 - (N - c1 - c2 - c3) / N)
    if c3 > 0:
        temp += func(c1, c2 + 1, c3 - 1) * (c3 / N) / \
            (1 - (N - c1 - c2 - c3) / N)

    dp[c1][c2][c3] = temp
    return temp


print(func(cnt1, cnt2, cnt3))


### FIXED CODE ###

# dp[c1][c2][c3]=
# 		(1個の皿がc1枚、2個の皿がc2枚、3個の皿がc3枚あるとき、全て食べるまでの操作回数の期待値)

N = int(input())
A = list(map(int, input().split()))
cnt1 = A.count(1)
cnt2 = A.count(2)
cnt3 = A.count(3)

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

# dp[c1][c2][c3]=1
# 	+dp[c1−1][c2][c3]∗(1個の皿が選ばれる確率)
# 	+dp[c1+1][c2−1][c3]∗(2個の皿が選ばれる確率)
# 	+dp[c1][c2+1][c3−1]∗(3個の皿が選ばれる確率)
# 	+dp[c1][c2][c3]∗(0個の皿が選ばれる確率)
# ↓式変形↓
# dp[c1][c2][c3]=1/(1−(0個の皿が選ばれる確率))
# 			+ dp[c1−1][c2][c3]*(1個の皿が選ばれる確率)/(1−(0個の皿が選ばれる確率))
# 			+ dp[c1+1][c2−1][c3]*(2個の皿が選ばれる確率)/(1−(0個の皿が選ばれる確率))
# 			+ dp[c1][c2+1][c3−1]*(3個の皿が選ばれる確率)/(1−(0個の皿が選ばれる確率))


def func(c1, c2, c3):
    if dp[c1][c2][c3] != -1:
        return dp[c1][c2][c3]

    # 繰り返し登場するので先に計算しておく
    prob0 = (N - c1 - c2 - c3) / N

    temp = 1 / (1 - prob0)
    if c1 > 0:
        temp += func(c1 - 1, c2, c3) * (c1 / N) / (1 - prob0)
    if c2 > 0:
        temp += func(c1 + 1, c2 - 1, c3) * (c2 / N) / (1 - prob0)
    if c3 > 0:
        temp += func(c1, c2 + 1, c3 - 1) * (c3 / N) / (1 - prob0)

    dp[c1][c2][c3] = temp
    return temp


print(func(cnt1, cnt2, cnt3))
### BUGGY CODE ###

N = int(input())

A_list = list(map(int, input().split()))

# ans = [A_list.index(i+1)+1 for i in range(N)]
#
# print(ans)

for i in range(N):
    print(A_list.index(i + 1) + 1,end=" ")


### FIXED CODE ###

import heapq
N = int(input())

A_list = list(map(int, input().split()))

list = [(A_list[i],i+1) for i in range(N)]
heapq.heapify(list)

for i in range(N):
    print(heapq.heappop(list)[1], end=" ")
### BUGGY CODE ###

n=int(input())
x=list(map(int,input().split()))
y=sorted(x)
a,b,c=y[n//2-1],y[n//2],y[:n//2]
for i in x:
  print(b if i in c else a)

### FIXED CODE ###

n=int(input())
x=list(map(int,input().split()))
y=sorted(x)
a,b=y[n//2-1],y[n//2]
for i in x:
  print(b if i<=a else a)
### BUGGY CODE ###

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

from collections import defaultdict, deque

def solve():
    N, K = map(int, input().split())
    H = defaultdict(int)
    for _ in range(N):
        H[int(input())] += 1
    if K in H.values():
        res = 0
    else:
        H = sorted(list(H.items()))
        res = float('inf')
        for i in range(len(H)):
            h = H[i][0]
            k = H[i][1]
            while k < K:
                i += 1
                if i < len(H):
                    k += H[i][1]
                else:
                     break
            else:
                h = H[i][0] - h
                res = min(res, h)
    return str(res)

if __name__ == '__main__':
    print(solve())

### FIXED CODE ###

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

from collections import defaultdict, deque

def solve():
    N, K = map(int, input().split())
    H = defaultdict(int)
    for _ in range(N):
        H[int(input())] += 1
    if K in H.values():
        res = 0
    else:
        H = sorted(list(H.items()))
        res = float('inf')
        i = 0
        j = 0
        b = H[0][0]
        t = H[0][0]
        k = H[0][1]
        h = 0
        while j < len(H)-1:
            if k < K:
                j += 1 
                k += H[j][1]
                h += H[j][0] - t
                t = H[j][0]
            if k >= K:
                res = min(res, h)
                k -= H[i][1]
                i += 1
                h -= H[i][0] - b
                b = H[i][0]

    return str(res)

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

from fractions import Fraction
n=int(input())
x=list(map(int,input().split()))
l=[1]
for i in range(1,n-1):
    l.append(l[-1]+Fraction(1,i+1))
#print(l)

for i in range(n-1):
    l[i]*=x[i+1]-x[i]

ans=sum(l)
for i in range(1,n):
    ans=ans*i%(10**9+7)
print(ans)

### FIXED CODE ###

import math
n=int(input())
a=list(map(int,input().split()))
ans=math.factorial(n-1)%(10**9+7)

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

c=0
for i in range(1,n):
    c+=(a[-1]-a[i-1])*modinv(i, mod=10**9+7)
print(ans*c%(10**9+7))
### BUGGY CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
q=[p[i]*(p[i]+1)/2 for i in range(n)]
def Sum(i,k):
  t=0
  for j in range(k):
    t += q[i+j]/p[i+j]
  return t
li=[]
ans=0
for i in range(n-k+1):
  ans = max(ans,Sum(i,k))
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
for i in range(n-k+1):
  if i==0:
    s=sum(p[:k])
    m=s
  else:
    s=s+p[i+k-1]-p[i-1]
    m = max(m,s)
print((m+k)/2)
### BUGGY CODE ###

def main():
    n = int(input())
    words = {}
    for _ in range(n):
        a = input()
        if a in words:
            words[a] += 1
        else:
            words[a] = 1
    results = [kv[0] for kv in words.items() if kv[1] == max(words.values())]
    results.sort()
    print(' '.join(map(str, results)))


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n = int(input())
    words = {}
    for _ in range(n):
        a = input()
        if a in words:
            words[a] += 1
        else:
            words[a] = 1
    max_val = 0
    results = []
    for i in words.keys():
        if words[i] > max_val:
            max_val = words[i]
            results = []
            results.append(i)
        elif words[i] == max_val:
            results.append(i)

            # results = [key
            #            for key in words.keys() if words[key] == max(words.values())]
            # results.sort()
    results.sort()
    print('\n'.join(map(str, results)))


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

import heapq

n, m = list(map(int, input().split()))
cards = list(map(int, input().split()))
heapq.heapify(cards)
queries = []
for i in range(m):
    q = list(map(int, input().split()))
    queries.append(q)

for q in queries:
    b, c = q
    cnt = 0
    while cnt < b:
        if cards[0] < c:
            heapq.heappop(cards)
            heapq.heappush(cards, c)
            cnt += 1
        else:
            break

ans = 0
for i in range(n):
    ans += cards[i]

print(ans)


### FIXED CODE ###

import heapq

n, m = list(map(int, input().split()))
cards = list(map(int, input().split()))
cards.sort()

queries = []
for i in range(m):
    q = list(map(int, input().split()))
    queries.append(q)
queries.sort(key=lambda x: x[1])
queries.reverse()

ans = 0
pos = 0
for q in queries:
    b, c = q
    if cards[min(pos+b-1, n-1)] < c:
        # print('a')
        pos = pos + b
        ans += c * (b - max(0, pos-n))
        if pos >= n:
            break
    else:
        for i in range(b):
            if cards[pos+i] < c:
                # print('b')
                ans += c
            else:
                # print('c')
                pos += i
                for j in range(pos, n):
                    ans += cards[j]

                pos = n
                break
        break

if pos < n:
    for j in range(pos, n):
        ans += cards[j]

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

from collections import deque
 
def main(*args, **kwargs):
    # Initialize data
    H, W = map(int, input().split())
    total_cells = H * W
    existing_black_cells = 0
 
    grid = []
    for i in range(H):
        line = input()
        existing_black_cells += line.count('#')
        grid.append(line)
 
    # Initialize Search
    queue = deque()
    queue.append((0, 0))  # start point
    visited = set()
    movement = 0

    while len(queue) > 0:
        movement += 1
        for i in range(len(queue)):  # Process same level
            coodinate = queue.popleft()
            visited.add(coodinate)
            y = coodinate[0]
            x = coodinate[1]
 
            # Terminate condition
            if y == H - 1 and x == W - 1:
                print(total_cells - movement - existing_black_cells)
                return
 
            for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                X = x + dx
                Y = y + dy
                adjacent = (Y, X)
                if 0 <= X < W and 0 <= Y < H and grid[Y][X] == '.' and adjacent not in visited:
                    queue.append(adjacent)
    print(-1)
    return
main()

### FIXED CODE ###

import sys
from collections import deque
    
def main(*args, **kwargs):
    # Initialize data
    H, W = map(int, sys.stdin.readline().split())
    total_cells = H * W
    existing_black_cells = 0
 
    grid = []
    for i in range(H):
        line = sys.stdin.readline()
        existing_black_cells += line.count('#')
        grid.append(line)
 
    # Initialize Search
    queue = deque()
    queue.append((0, 0))  # start point
    visited = set()
    visited.add((0, 0))
    movement = 0
 
    while len(queue) > 0:
        movement += 1
        for i in range(len(queue)):  # Process same level
            coodinate = queue.popleft()
            y = coodinate[0]
            x = coodinate[1]
 
            # Terminate condition
            if y == H - 1 and x == W - 1:
                print(total_cells - movement - existing_black_cells)
                return
 
            for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                X = x + dx
                Y = y + dy
                adjacent = (Y, X)
                if 0 <= X < W and 0 <= Y < H and grid[Y][X] == '.' and adjacent not in visited:
                    queue.append(adjacent)
                    visited.add(adjacent)
    print(-1)
    return
main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def linput():
    return [int(x) for x in input().split()]

n = int(input())
s = input().rstrip()

from collections import Counter

r = []
g = []
b = []



for i in range(n):
    if s[i] == "R":
        r.append(i)
    elif s[i] == "G":
        g.append(i)
    else:
        b.append(i)

cr = Counter(r)
cg = Counter(g)
cb = Counter(b)

import bisect
from copy import deepcopy
ans = 0
for i in range(n):
    for j in range(i + 1, n):
        if s[i] == s[j]:
            continue
        ng = j + (j - i)
        if s[i] == "R" and s[j] == "G":
            l = deepcopy(b)
            c = cb
        elif s[i] == "R" and s[j] == "B":
            l = deepcopy(g)
            c = cg
        elif s[i] == "G" and s[j] == "R":
            l = deepcopy(b)
            c = cb
        elif s[i] == "G" and s[j] == "B":
            l = deepcopy(r)
            c = cr
        elif s[i] == "B" and s[j] == "R":
            l = deepcopy(g)
            c = cg
        elif s[i] == "B" and s[j] == "G":
            l = deepcopy(r)
            c = cr
        ans += len(l) - bisect.bisect_right(l, j)
        ans -= c[j + (j - i)]

print(ans)






### FIXED CODE ###

import sys
input = sys.stdin.readline

def linput():
    return [int(x) for x in input().split()]

n = int(input())
s = input().rstrip()

from collections import Counter

r = [0] * (n + 1)
g = [0] * (n + 1)
b = [0] * (n + 1)



for i in range(1, n + 1):
    if s[i - 1] == "R":
        r[i] = r[i - 1] + 1
    else:
        r[i] = r[i - 1]
    if s[i - 1] == "G":
        g[i] = g[i - 1] + 1
    else:
        g[i] = g[i - 1]
    if s[i - 1] == "B":
        b[i] = b[i - 1] + 1
    else:
        b[i] = b[i - 1]

ans = 0
for i in range(n):
    for j in range(i + 1, n - 1):
        if s[i] == s[j]:
            continue
        ng = j + (j - i) + 1
        if s[i] == "R" and s[j] == "G":
            l = b
        elif s[i] == "R" and s[j] == "B":
            l = g
            #c = cg
        elif s[i] == "G" and s[j] == "R":
            l = b
            #c = cb
        elif s[i] == "G" and s[j] == "B":
            l = r
            #c = cr
        elif s[i] == "B" and s[j] == "R":
            l = g
            #c = cg
        elif s[i] == "B" and s[j] == "G":
            l = r
            #c = cr
        ans += l[n] - l[j + 1]
        if ng < n + 1:
            ans -= l[ng] - l[ng - 1]
        #print(ans)

print(ans)