Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD

MAX_N = 110000

memo = [-1 for _ in range(MAX_N)]
def rec(n):
    if n == 0: return 0
    if memo[n] != -1: return memo[n]

    res = n

    pow6 = 1
    while pow6 <= n:
        res = min(res, rec(n-pow6)+1)
        pow6 *= 6
    pow9 = 1
    while pow9 <= n:
        res = min(res, rec(n-pow9)+1)
        pow9 *= 9
    memo[n] = res
    return res


N = iin()
print(rec(N))



Fixed submission:
max_n = 100000

N = int(input())

dp = [N for _ in range(N+1)]
dp[0] = 0
for n in range(1, N+1):
    for pow6 in range(n+1):
        if 6 ** pow6 <= n:
            dp[n] = min(dp[n], dp[n - 6 ** pow6] + 1)
        else:
            break

    for pow9 in range(n+1):
        if 9 ** pow9 <= n:
            dp[n] = min(dp[n], dp[n - 9 ** pow9] + 1)
        else:
            break
print(dp[N])
Buggy python submission (verdict: Time Limit Exceeded):
X = int(input())

max_v = 1

for i in range(2, X+1):
    for j in range(2, X+1):
        if i ** j <= X:
            max_v = max(max_v, i ** j)
print(max_v)



Fixed submission:
X = int(input())

max_v = 1

for i in range(2, X+1):
    for j in range(2, X+1):
        if i ** j <= X:
            max_v = max(max_v, i ** j)
        else:
            break
print(max_v)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
K = int(input())

s_set = set()

for i in range(len(s)):
    sub_s = s[i]
    s_set.add(sub_s)
    for j in range(i+1, len(s)):
        sub_s += s[j]
        s_set.add(sub_s)

print(sorted(s_set)[K-1])

        


Fixed submission:
s = input()
K = int(input())

s_set = set()

for i in range(len(s)):
    sub_s = s[i]
    s_set.add(sub_s)
    for j in range(i+1, len(s)):
        sub_s += s[j]
        s_set.add(sub_s)
        if len(sub_s) == 5:
            break


print(sorted(s_set)[K-1])
Buggy python submission (verdict: Time Limit Exceeded):
import itertools

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

c = [0] * (N+1)

for i in range(N):
    c[i+1] = c[i] + A[i]

cnt = 0
for i in range(N+1):
    for j in range(i+1, N+1):
        if c[j] - c[i] == 0:
            cnt += 1
print(cnt)


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

c = [0] * (N+1)

for i in range(N):
    c[i+1] = c[i] + A[i]
cnt = {}
for i in range(0,N+1):
    if c[i] not in cnt:
        cnt[c[i]] = 1
    else:
        cnt[c[i]] += 1
count = 0
for v in cnt.values():
    count += v * (v-1) // 2
print(count)
Buggy python submission (verdict: Runtime Error):
A,B,K = map(int, input().split())

AB = range(A,B+1)

tail = len(AB)

for i in range(K):
    print(AB[i])

for i in range(tail - K, tail):
    print(AB[i])



Fixed submission:
A,B,K = map(int, input().split())

AB = range(A,B+1)
tail = len(AB)
AB_L = set(AB[0:min(K,tail)])
AB_R = set(AB[max(0,tail-K):tail])
AB_SL = sorted(AB_L | AB_R)

for ab in AB_SL:
    print(ab)

Buggy python submission (verdict: Time Limit Exceeded):
A,B,K = map(int, input().split())

AB = range(A,B+1)

tail = len(AB)
for i in range(tail):
    if i < K or tail - K <= i:
        print(AB[i])



Fixed submission:
A,B,K = map(int, input().split())

AB = range(A,B+1)
tail = len(AB)
AB_L = set(AB[0:min(K,tail)])
AB_R = set(AB[max(0,tail-K):tail])
AB_SL = sorted(AB_L | AB_R)

for ab in AB_SL:
    print(ab)
Buggy python submission (verdict: Time Limit Exceeded):
import collections

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

c = collections.Counter(A)

cnt = 0
if K < len(c.keys()):
    for i in range(1,abs(len(c.keys()) - K)+1):
            cnt += c.most_common()[-i][1]
print(cnt)



Fixed submission:
import collections

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

c = collections.Counter(A)

cnt = 0
most_common = c.most_common()
if K < len(c.keys()):
    for i in range(1,abs(len(c.keys()) - K)+1):
            cnt += most_common[-i][1]
print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
import collections

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

c = collections.Counter(A)

cnt = 0
if K < len(c.keys()):
    for i in range(1,abs(len(c.keys()) - K)+1):
            cnt += c.most_common()[-i][1]
print(cnt)



Fixed submission:
import collections

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

c = collections.Counter(A)

cnt = 0
most_common = c.most_common()
if K < len(c.keys()):
    for i in range(1,abs(len(c.keys()) - K)+1):
            cnt += most_common[-i][1]
print(cnt)
Buggy python submission (verdict: Runtime Error):
N = int(input())
F = [list(map(int, input().split())) for _ in range(N)]
P = [list(map(int, input().split())) for _ in range(N)]

max_v = -(10 ** 10)
for i in range(1,2**10):

    S_cnt = [0] * 10
    for j in range(10):
        if i % 2 == 1:
            for k in range(N):
                if F[k][j] == 1:
                    S_cnt[k] += 1
        i //= 2
    print

    tmp_v = 0
    for j in range(N):
        tmp_v += P[j][S_cnt[j]]
    max_v = max(max_v, tmp_v)

print(max_v)

Fixed submission:
N = int(input())
F = [list(map(int, input().split())) for _ in range(N)]
P = [list(map(int, input().split())) for _ in range(N)]

max_v = -(10 ** 10)
for i in range(1,2**10):

    S_cnt = [0] * N 
    for j in range(10):
        if i % 2 == 1:
            for k in range(N):
                if F[k][j] == 1:
                    S_cnt[k] += 1
        i //= 2

    tmp_v = 0
    for j in range(N):
        tmp_v += P[j][S_cnt[j]]
    max_v = max(max_v, tmp_v)

print(max_v)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = sorted(map(int, input().split()))
B = sorted(map(int, input().split()))
C = sorted(map(int, input().split()), reverse=True)

cnt = 0
for i in range(N):
    if C[i] <= B[0]:
        break
    for j in range(N):
        if C[i] > B[j]:
            for k in range(N):
                if B[j] > A[k]:
                    cnt+= 1
                else:
                    break
        else:
            break
print(cnt)


Fixed submission:
from  bisect import bisect_left, bisect_right

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

cnt = 0
for b in B:
    a_cnt = bisect_left(A, b)
    c_cnt = N - bisect_right(C, b)
    cnt += a_cnt * c_cnt
print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = sorted(map(int, input().split()))
B = sorted(map(int, input().split()))
C = sorted(map(int, input().split()))

cnt = 0
for i in range(N):
        for j in range(N):
            if C[i] > B[j]:
                for k in range(N):
                    if B[j] > A[k]:
                        cnt+= 1
                    else:
                        break
            else:
                break
print(cnt)


Fixed submission:
from  bisect import bisect_left, bisect_right

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

cnt = 0
for b in B:
    a_cnt = bisect_left(A, b)
    c_cnt = N - bisect_right(C, b)
    cnt += a_cnt * c_cnt
print(cnt)
Buggy python submission (verdict: Runtime Error):
S = input()
T = input()

t_len = len(T)
found = False
for i in range(len(S)-len(T), -1,-1):
    for j in range(len(T)):
        if S[i+j] != T[j] and S[i+j] != '?':
            break
    else:
        if i + t_len == len(S):
            S = S[:i] + T
        else:
            S = S[:i] + T + S[i+tlen:]
        found = True
    if found:
        print(S.replace('?','a'))
        break
else:
    print('UNRESTORABLE')



Fixed submission:
S = input()
T = input()

t_len = len(T)
found = False
for i in range(len(S)-len(T), -1,-1):
    for j in range(len(T)):
        if S[i+j] != T[j] and S[i+j] != '?':
            break
    else:
        if i + t_len == len(S):
            S = S[:i] + T
        else:
            S = S[:i] + T + S[i+t_len:]
        found = True
    if found:
        print(S.replace('?','a'))
        break
else:
    print('UNRESTORABLE')
Buggy python submission (verdict: Runtime Error):
import fractions

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

def lcm(a,b):
    return int(a * b / fractions.gcd(a,b))

ans = T[0]

for i in range(1, N):
    ans = lcm(ans, T[i])

print(ans)


Fixed submission:
import fractions

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

def lcm(a,b):
    return a * b // fractions.gcd(a,b)

ans = T[0]

for i in range(1, N):
    ans = lcm(ans, T[i])

print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
a = list(map(int, input().split()))

cnt_of_4 = 0
cnt_of_2 = 0
cnt_of_1 = 0
for i in range(N):
    if a[i] % 4 == 0:
        cnt_of_4 += 1
    elif a[i] == 2:
        cnt_of_2 += 1
    else:
        cnt_of_1 += 1

if cnt_of_4 == N//2:
    print('Yes')
else:
    if cnt_of_1 < cnt_of_4:
        cnt_of_2 = cnt_of_2 - (cnt_of_4-cont_of1)
    if cnt_of_4 * 2 + ((cnt_of_2//2)*2) >= N:
        print('Yes')
    else:
        print('No')
    


Fixed submission:
N = int(input())
a = list(map(int, input().split()))

cnt_of_4 = 0
cnt_of_2 = 0
for i in range(N):
    if a[i] % 4 == 0:
        cnt_of_4 += 1
    elif a[i] % 2 ==  0:
        cnt_of_2 += 1

if cnt_of_4 >= N//2 or cnt_of_4 *2 + cnt_of_2 >= N:
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Time Limit Exceeded):
N,M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]

first_to = []
to_dest = []

for ab in AB:
    if ab[0] == 1:
        first_to.append(ab[1])
    elif ab[1] == N:
        to_dest.append(ab[0])

for f in first_to:
    if f in to_dest:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')


Fixed submission:
N,M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]

first_to = []
to_dest = []

for ab in AB:
    if ab[0] == 1:
        first_to.append(ab[1])
    elif ab[1] == N:
        to_dest.append(ab[0])
first_to = set(first_to)
to_dest = set(to_dest)

for f in first_to:
    if f in to_dest:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Buggy python submission (verdict: Time Limit Exceeded):
N,M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]

first_to = []
to_dest = []

for ab in AB:
    if ab[0] == 1:
        first_to.append(ab[1])
    elif ab[1] == N:
        to_dest.append(ab[0])

for f in first_to:
    if f in to_dest:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')


Fixed submission:
N,M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]

first_to = []
to_dest = []

for ab in AB:
    if ab[0] == 1:
        first_to.append(ab[1])
    elif ab[1] == N:
        to_dest.append(ab[0])
first_to = set(first_to)
to_dest = set(to_dest)

for f in first_to:
    if f in to_dest:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Buggy python submission (verdict: Time Limit Exceeded):
N,M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]

first = []

for ab in AB:
    if ab[0] == 1:
        first.append(ab[1])

for ab in AB:
    if ab[0] in first and ab[1] == N:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')



Fixed submission:
N,M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]

first_to = []
to_dest = []

for ab in AB:
    if ab[0] == 1:
        first_to.append(ab[1])
    elif ab[1] == N:
        to_dest.append(ab[0])
first_to = set(first_to)
to_dest = set(to_dest)

for f in first_to:
    if f in to_dest:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
b = []

for i in range(n):
    b.append(a[i])
    b.reverse()

print(*b)


Fixed submission:
from collections import deque

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

for i in range(n):
    if i % 2 == 0:
        b.append(a[i])
    else:
        b.appendleft(a[i])

if n % 2 == 1:
    b.reverse()

print(*b)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(1000000)

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

if abs(N-M) > 1:
    print(0)
    exit()

def frac(n):
    if n == 1: return 1
    return n * frac(n-1)

n_frac = frac(N)
m_frac = frac(M)
if N-M == 0:
    print((n_frac*m_frac)*2)
else:
    print(n_frac*m_frac)





Fixed submission:
from math import factorial

N,M = map(int, input().split())
mod = 10 ** 9 + 7

if abs(N-M) > 1:
    print(0)
    exit()

n_frac = factorial(N) 
m_frac = n_frac
if N-M == 0:
    print((n_frac*m_frac)*2%mod)
else:
    if N > M:
        m_frac //= N
    else:
        m_frac *=  M
    print(n_frac*m_frac%mod)
Buggy python submission (verdict: Runtime Error):

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

def get_color(point):
    color = ''
    if 400 > point:
        color = 'grey'
    elif 800 > point:
        color = 'brown'
    elif 1200 > point:
        color = 'green'
    elif 1600 > point:
        color = 'light blue'
    elif 2000 > point:
        color = 'blue'
    elif 2400 > point:
        color = 'yellow'
    elif 2800 > point:
        color = 'orange'
    elif 3200 > point:
        color = 'red'
    else:
        color = 'free'
    return color
dict = {}
for i in range(N):
    color = get_color(a[i])
    if color not in dict.keys():
        dict[color] = 1
    else:
        dict[color] += 1

min_cnt = 0
max_cnt = 0
if 'free' not in dict.keys():
    min_cnt = max_cnt = len(dict.keys())
else:
    min_cnt = len(dict.keys())-1
    max_cnt = min(8, min_cnt + len(dict['free']))

print(min_cnt, max_cnt)


Fixed submission:
N = int(input())
a = list(map(int, input().split()))

def get_color(point):
    color = ''
    if 400 > point:
        color = 'grey'
    elif 800 > point:
        color = 'brown'
    elif 1200 > point:
        color = 'green'
    elif 1600 > point:
        color = 'light blue'
    elif 2000 > point:
        color = 'blue'
    elif 2400 > point:
        color = 'yellow'
    elif 2800 > point:
        color = 'orange'
    elif 3200 > point:
        color = 'red'
    else:
        color = 'free'
    return color
dict = {}
for i in range(N):
    color = get_color(a[i])
    if color not in dict.keys():
        dict[color] = 1
    else:
        dict[color] += 1

min_cnt = 0
max_cnt = 0
if 'free' not in dict.keys():
    min_cnt = max_cnt = len(dict.keys())
else:
    min_cnt = max(1, len(dict.keys())-1)
    max_cnt = len(dict.keys())-1 + dict['free']

print(min_cnt, max_cnt)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
s = [int(input()) for _ in range(N)]

MAX_VALUE = 100001
dp = [[False for _ in range(MAX_VALUE)] for _ in range(N+1)]

dp[0][0] = True
for i in range(N):
    score = s[i]
    for j in range(MAX_VALUE):
        dp[i+1][j] |= dp[i][j]
        if j >= score:
            dp[i+1][j] |= dp[i][j-score]
ans = 0

for i in range(MAX_VALUE):
    if dp[N][i] == True and i % 10 != 0:
        ans = i
print(ans)



Fixed submission:
N = int(input())
s = [int(input()) for _ in range(N)]

MAX_VALUE = 100001
dp = [[False for _ in range(MAX_VALUE)] for _ in range(N+1)]

dp[0][0] = True
for i in range(N):
    score = s[i]
    for j in range(MAX_VALUE):
        dp[i+1][j] |= dp[i][j]
        if j >= score:
            dp[i+1][j] |= dp[i][j-score]
ans = 0

for i in range(MAX_VALUE):
    if dp[N][i] == True and i % 10 != 0:
        ans = i
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

p = 1

for i in range(1, N+1):
    p *= i

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

Fixed submission:
N = int(input())

p = 1
div = 10 ** 9 + 7
for i in range(1, N+1):
    p = (p * i) % div

print(p % div)
Buggy python submission (verdict: Runtime Error):
N,M = map(int, input().split())

A = [input() for _ in range(N)]
B = [input() for _ in range(M)]

b_index = 0
for i in range(N):
    for j in range(len(A[i])):
        if A[i][j] == B[0][0]:
            for i2 in range(M):
                for j2 in range(len(B[i2])):
                    if A[i+i2][j+j2] != B[i2][j2]:
                        break
                else:
                    continue
                break
            else:
                print('Yes')
                exit()
print('No')


                



Fixed submission:
N,M = map(int, input().split())

A = [input() for _ in range(N)]
B = [input() for _ in range(M)]

b_index = 0
for i in range(N):
    for j in range(len(A[i])):
        if A[i][j] == B[0][0]:
            for i2 in range(M):
                for j2 in range(len(B[i2])):
                    if i+i2 > N-1 or j+j2 > len(A[i+i2])-1:
                        break
                    elif A[i+i2][j+j2] != B[i2][j2]:
                        break
                else:
                    continue
                break
            else:
                print('Yes')
                exit()
print('No')
Buggy python submission (verdict: Time Limit Exceeded):
K,S = map(int, input().split())

ans = 0
for x in range(0,K+1):
    for y in range(0,K+1):
        if x + y > S:
            break
        for z in range(0,K+1):
            if x + y + z == S:
                ans += 1
            if x + y + z > S:
                break

print(ans)


Fixed submission:
K,S = map(int, input().split())

ans = 0
for x in range(0,K+1):
    for y in range(0,K+1):
        z = S - x - y
        if 0 <= z <= K:
            ans += 1

print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
a  = list(map(int,input().split()))
cnt = {}
for i in range(n):
    if a[i] not in cnt:cnt[a[i]] = [i]
    else:cnt[a[i]].append(i)

    
lcnt,rcnt = 0,0
ans = 0
for val,ind in res:
    if ind-lcnt < n-ind-1-rcnt:
        
        ans +=val*(n-ind-1-rcnt)
        rcnt+=1
    else:
        ans +=val*(ind - lcnt)
        lcnt+=1
print(ans)
        
        
    
    

Fixed submission:
n = int(input())
a = list(map(int,input().split()))
num  = []
for i in range(n):
    num.append([a[i],i])
num.sort(reverse = True)
dp = [[0]*(n+1)for i in range(n+1)]
ans = 0
for l in range(n):
    for r in range(n):
        if l+r == n:
            ans = max(ans,dp[l][r])
            break
        dp[l+1][r] = max(dp[l+1][r], dp[l][r] + num[l+r][0]*abs(num[l+r][1]-l))
        dp[l][r+1] = max(dp[l][r+1],dp[l][r]+num[l+r][0]*abs(num[l+r][1]-n+1+r))
print(ans)

Buggy python submission (verdict: Runtime Error):
n = int(input())
a  = list(map(int,input().split()))
cnt = {}
for i in range(n):
    if a[i] not in cnt:cnt[a[i]] = [i]
    else:cnt[a[i]].append(i)

    
lcnt,rcnt = 0,0
ans = 0
for val,ind in res:
    if ind-lcnt < n-ind-1-rcnt:
        
        ans +=val*(n-ind-1-rcnt)
        rcnt+=1
    else:
        ans +=val*(ind - lcnt)
        lcnt+=1
print(ans)
        
        
    
    

Fixed submission:
n = int(input())
a = list(map(int,input().split()))
num  = []
for i in range(n):
    num.append([a[i],i])
num.sort(reverse = True)
dp = [[0]*(n+1)for i in range(n+1)]
ans = 0
for l in range(n):
    for r in range(n):
        if l+r == n:
            ans = max(ans,dp[l][r])
            break
        dp[l+1][r] = max(dp[l+1][r], dp[l][r] + num[l+r][0]*abs(num[l+r][1]-l))
        dp[l][r+1] = max(dp[l][r+1],dp[l][r]+num[l+r][0]*abs(num[l+r][1]-n+1+r))
print(ans)

Buggy python submission (verdict: Runtime Error):
n = int(input())
a  = list(map(int,input().split()))
cnt = {}
for i in range(n):
    if a[i] not in cnt:cnt[a[i]] = [i]
    else:cnt[a[i]].append(i)

    
lcnt,rcnt = 0,0
ans = 0
for val,ind in res:
    if ind-lcnt < n-ind-1-rcnt:
        
        ans +=val*(n-ind-1-rcnt)
        rcnt+=1
    else:
        ans +=val*(ind - lcnt)
        lcnt+=1
print(ans)
        
        
    
    

Fixed submission:
n = int(input())
a = list(map(int,input().split()))
num  = []
for i in range(n):
    num.append([a[i],i])
num.sort(reverse = True)
dp = [[0]*(n+1)for i in range(n+1)]
ans = 0
for l in range(n):
    for r in range(n):
        if l+r == n:
            ans = max(ans,dp[l][r])
            break
        dp[l+1][r] = max(dp[l+1][r], dp[l][r] + num[l+r][0]*abs(num[l+r][1]-l))
        dp[l][r+1] = max(dp[l][r+1],dp[l][r]+num[l+r][0]*abs(num[l+r][1]-n+1+r))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = input()
words = [[0]*3for _ in range(n)] #i以降のR,G,Bの数(i含まず)
for i in range(n-2,-1,-1):
    if s[i+1] == 'R':
        words[i][0]+=1
    elif s[i+1] == 'G':
        words[i][1] +=1
    else:words[i][2] +=1
    words[i][0] +=words[i+1][0]
    words[i][1] +=words[i+1][1]
    words[i][2] +=words[i+1][2]
ans = 0
for i in range(n):
    for j in range(i+1,n):
        
        if s[i] == 'R':
            if s[j] == 'G':
                ans += words[j][2]
                if j+j-i >n-1:continue
                if s[j+(j-i)] == 'B':ans-=1
            if s[j] == 'B':
                ans += words[j][1]
                if j+j-i >n-1:continue
                if s[j+(j-i)] == 'G':ans-=1
        if s[i] == 'G':
            if s[j] == 'R':
                ans += words[j][2]
                if j+j-i >n-1:continue
                if s[j+(j-i)] == 'B':ans-=1
            if s[j] == 'B':
                ans += words[j][0]
                if j+j-i >n-1:continue
                if s[j+(j-i)] == 'R':ans-=1
        if s[i] == 'B':
            if s[j] == 'G':
                ans += words[j][0]
                if j+j-i >n-1:continue
                if s[j+(j-i)] == 'R':ans-=1
            if s[j] == 'R':
                ans += words[j][1]
                if j+j-i >n-1:continue
                if s[j+(j-i)] == 'G':ans-=1
print(ans)
 


        

        

        
        
    

Fixed submission:
n = int(input())
s = input()
words = [[0]*3for _ in range(n)] #i以降のR,G,Bの数(i含まず)
for i in range(n-2,-1,-1):
    if s[i+1] == 'R':
        words[i][0]+=1
    elif s[i+1] == 'G':
        words[i][1] +=1
    else:words[i][2] +=1
    words[i][0] +=words[i+1][0]
    words[i][1] +=words[i+1][1]
    words[i][2] +=words[i+1][2]
ans = 0
for i in range(n):
    for j in range(i+1,n):
        
        if s[i] == 'R':
            if s[j] == 'G':
                ans += words[j][2]
                if j+j-i >n-1:continue
                if s[j+(j-i)] == 'B':ans-=1
            if s[j] == 'B':
                ans += words[j][1]
                if j+j-i >n-1:continue
                if s[j+(j-i)] == 'G':ans-=1
        if s[i] == 'G':
            if s[j] == 'R':
                ans += words[j][2]
                if j+j-i >n-1:continue
                if s[j+(j-i)] == 'B':ans-=1
            if s[j] == 'B':
                ans += words[j][0]
                if j+j-i >n-1:continue
                if s[j+(j-i)] == 'R':ans-=1
        if s[i] == 'B':
            if s[j] == 'G':
                ans += words[j][0]
                if j+j-i >n-1:continue
                if s[j+(j-i)] == 'R':ans-=1
            if s[j] == 'R':
                ans += words[j][1]
                if j+j-i >n-1:continue
                if s[j+(j-i)] == 'G':ans-=1
print(ans)