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

#!/usr/bin/env python3
import sys

def solve(N: int, M: int, K: int, A: "List[int]", B: "List[int]"):
    if sum(A) + sum(B) < K:
        print(N + M)
        return
    weightA = 0
    tmp_A = N
    for idx, a in enumerate(A):
        if weightA + a > K:
            tmp_A = idx
            break
        else:
            weightA += a
    max_count = current_count = tmp_A
    len_A = tmp_A

    weightB = 0
    for b in B:
        if weightA + weightB > K:
            break

        if len_A==0 and weightA + weightB + b > K:
            break

        if weightA + weightB > K:
            break

        if weightA + weightB + b <= K:
            weightB += b
            current_count += 1

        else:
            while weightA + weightB + b > K:
                if len_A>0:
                    weightA -= A[len_A-1]
                    len_A -= 1
                    current_count -= 1

            if weightA + weightB + b <= K:
                weightB += b
                current_count += 1
        max_count = max(max_count, current_count)


    print(max_count)
    return


# Generated by 1.1.7.1 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
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    B = [int(next(tokens)) for _ in range(M)]  # type: "List[int]"
    solve(N, M, K, A, B)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys


N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a, b = [0], [0]

for i in range(N):
    a.append(a[i] + A[i])
for i in range(M):
    b.append(b[i] + B[i])
ans, j = 0, M
for i in range(N+1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans, i + j)
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.buffer.readline
def dfs(G,v,p):
    for nv in G[v]:
        if(nv==p):
            continue
        point[nv]+=point[v]
        dfs(G,nv,v)

N,Q=map(int,input().split())
G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
point=[0]*N
for i in range(Q):
    p,x=map(int,input().split())
    point[p-1]+=x
dfs(G,0,-1)
print(*point)


### FIXED CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)
def dfs(G,s,p):
    for nv in G[s]:
        if(nv==p):
            continue
        Count[nv]+=Count[s]
        dfs(G,nv,s)
    
N,Q=map(int,input().split())
Count=[0]*N
G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
for i in range(Q):
    p,x=map(int,input().split())
    Count[p-1]+=x
dfs(G,0,-1)
print(*Count)
### BUGGY CODE ###

import math

K = int(input())

def gcd_(a,b,c):
    t = math.gcd(a,b)
    return(math.gcd(t,c))


sum = 0

for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            sum += gcd_(a,b,c)

print(sum)            


### FIXED CODE ###

import math

K = int(input())

gcd2 = [[0 for i in range(K)] for i in range(K)]

for i in range(K):
    for j in range(K):
        gcd2[i][j] = math.gcd(i+1,j+1)

sum = 0
for i in range(K):
    for j in range(K):
        for k in range(K):
            sum += math.gcd(gcd2[i][j],k+1)

print(sum)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000)

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

num_dict = {
    1: 2,
    2: 5,
    3: 5,
    4: 4,
    5: 5,
    6: 6,
    7: 3,
    8: 7,
    9: 6
}

# Aの各要素の画数
count_list = [num_dict[a] for a in A]

# 最小の画数
min_matches = min(count_list)

# 画数の最小の値のうち最大の数値
min_num_list = []
[min_num_list.append(a) for a in A if num_dict[a] == min_matches]
min_num = max(min_num_list)


# 数値とあまり消化数のペア
A.sort(reverse=True)
res = {a: num_dict[a]-min_matches for a in A}


def dfs(nums, target, num_count):
    if len(nums) > num_count:
        return None

    if target > 0:
        for a in A:
            ret = dfs(nums+[a], target-res[a], num_count)
            if ret is not None:
                return ret
        return None
    elif target == 0:
        return nums
    else:
        return None


for num_count in range(N//min_matches, 0, -1):
    # あまりの本数
    mod = N - min_matches*num_count

    # あまりをどう分配するか(DFS)
    share = dfs([], mod, num_count)
    if share is not None:
        out_list = sorted([min_num]*(num_count-len(share))+share, reverse=True)
        out_list = [str(item) for item in out_list]
        print(''.join(out_list))
        break


### FIXED CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10000)


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

num_dict = {
    1: 2,
    2: 5,
    3: 5,
    4: 4,
    5: 5,
    6: 6,
    7: 3,
    8: 7,
    9: 6
}
A.sort(reverse=True)

# dpを計算
dp = defaultdict(lambda: -1e18)
dp[0] = 0

for i in range(2, N+1):
    dp[i] = max([dp[i-num_dict[a]]+1 for a in A])

num_count = dp[N]

out_list = []
res_N = N
for _ in range(num_count):
    for a in A:
        if dp[res_N]-1 == dp[res_N-num_dict[a]]:
            out_list.append(str(a))
            res_N = res_N - num_dict[a]
            break

print(''.join(out_list))
### BUGGY CODE ###

def mmult(A, B):
    global mod
    n, m, l = len(A), len(B), len(B[0])
    ret = [[0]*l for _ in range(n)]
    for i in range(n):
        for j in range(m):
            for k in range(l):
                ret[i][k] = (ret[i][k]+A[i][j]*B[j][k])%mod
    return ret
def mpow(A, n):
    if n == 0: return [[1 if i==j else 0 for j in range(len(A))] for i in range(len(A))]
    if n % 2: return mmult(mpow(A, n-1), A)
    return mpow(mmult(A, A), n//2)

mod = 10**9+7
N, K = map(int, input().split())
X = [[int(a) for a in input().split()] for _ in range(N)]
print(sum([sum(x) for x in mpow(X, K)]) % mod)

### FIXED CODE ###

def mmult(A, B):
    global mod
    n, m, l = len(A), len(B), len(B[0])
    ret = [[0]*l for _ in range(n)]
    for i in range(n):
        for j in range(m):
            for k in range(l):
                ret[i][k] = (ret[i][k]+A[i][j]*B[j][k])%mod
    return ret
def mpow(A, n):
    if n == 0: return [[1 if i==j else 0 for j in range(len(A))] for i in range(len(A))]
    if n % 2: return mmult(mpow(A, n-1), A)
    return mpow(mmult(A, A), n//2)

mod = 10**9+7
N, K = map(int, input().split())
X = [[int(a) for a in input().split()] for _ in range(N)]
print(sum([sum(x) for x in mpow(X, K)]) % mod)
### BUGGY CODE ###

# AOJ 0056 Goldbach's Conjecture
# Python3 2018.6.16 bal4u

MAX = 50001
HALF = 25000

prime = [True]*MAX
def sieve(max):
	for i in range(4, max, 2):
		prime[i] = False
	sqrt = int(max**0.5)
	print('Sqrt=',sqrt)
	for i in range(3, sqrt, 2):
		if prime[i] is True:
			for j in range(i*i, max, i):
				prime[j] = False
sieve(MAX)

ans = [0]*(MAX*2)
ans[4] = 1
for i in range(3, MAX, 2):
	if prime[i]: ans[i+2] = 1

for i in range(3, HALF, 2):
	if prime[i]:
		for j in range(i, MAX, 2):
			if prime[j]: ans[i+j] += 1

while True:
	n = int(input())
	if n == 0: break
	print(ans[n])


### FIXED CODE ###

# AOJ 0056 Goldbach's Conjecture
# Python3 2018.6.16 bal4u

MAX = 50000
HALF = 2761			# prime[2760]=24989, prime[2761]=25013

prime = [
  3,  5,  7, 11, 13, 17, 19, 23, 29, 
 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 
 73, 79, 83, 89, 97,101,103,107,109,113, 
127,131,137,139,149,151,157,163,167,173, 
179,181,191,193,197,199,211,223 ]

sqp = [				# sqp[i] = prime[i]**2
  9,25,49,121,169,289,361,529,841,961,
1369,1681,1849,2209,2809,3481,3721,4489,5041,
5329,6241,6889,7921,9409,10201,10609,11449,11881,12769,
16129,17161,18769,19321,22201,22801,24649,26569,27889,29929,
32041,32761,36481,37249,38809,39601,44521,49729 ]

tbl = [0]*(MAX+1)	# zero if prime 
ans = [0]*(MAX+1)
ans[4] = 1

for i in range(47):
	for j in range(sqp[i], MAX, prime[i]): tbl[j] = 1;

for i in range(225, MAX+1, 2):
	if tbl[i] == 0: prime.append(i)

for i in range(HALF):
	j = i
	while True:
		k = prime[i]+prime[j]
		if k > MAX: break
		ans[k] += 1
		j += 1

while True:
	n = int(input())
	if n == 0: break
	if (n & 1) == 1: print(1-tbl[n-2])
	else: print(ans[n])
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 1
if 0 in a:
    ans = 0
else:
    for i in a:
        ans *= i
        if ans > 1000000000000000000:
            ans = -1
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 1
if 0 in a:
    ans = 0
else:
    for i in a:
        ans *= i
        if ans > 1000000000000000000:
            ans = -1
            break
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
A =[]
for _ in range(m):
    l,r = map(int,input().split())
    tmp = [i for i in range(l,r+1)]
    A += tmp

from collections import Counter
cnt = Counter(A)
ans = []

for k,v in cnt.items():
    if v == m:
        ans.append(k)
print(len(ans))


### FIXED CODE ###

n,m = map(int,input().split())
L = []
R = []

for _ in range(m):
    l,r = map(int,input().split())
    L.append(l)
    R.append(r)
tmp = min(R)-max(L)+1

if tmp >= 1:
    print(tmp)
else:
    print(0)
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Fri Feb  8 05:12:38 2019

@author: shinjisu
"""


def db(x):
    global debug
    if debug:
        print(x)


# スタックオーバーフロー
def gen(tstr):
    if len(tstr) <= len(S):
        for w in words:
            yield tstr + w
            for w2 in gen(tstr + w):
                yield w2


def solve():
    ans = False
    for genstr in gen(''):
        db(genstr)
        if genstr == S:
            ans = True
            break
    return ans


def solve2():
    stack = list(words)
    while stack != []:
        str = stack.pop()
        db(('pop', str))
        if len(str) < len(S):
            for w in words:
                stack.append(str+w)
        elif len(str) == len(S) and str == S:
            return True
    return False


debug = False
words = ('dream', 'dreamer', 'erase', 'eraser')
S = input()
db(S)
if solve2():
    print('YES')
else:
    print('NO')


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Fri Feb  8 05:12:38 2019

@author: shinjisu
"""


def db(x):
    global debug
    if debug:
        print(x)


# スタックオーバーフロー
def gen(tstr):
    if len(tstr) <= len(S):
        for w in words:
            yield tstr + w
            for w2 in gen(tstr + w):
                yield w2


# RE
def solve():
    ans = False
    for genstr in gen(''):
        db(genstr)
        if genstr == S:
            ans = True
            break
    return ans


# TLE
def solve2():
    stack = list(words)
    while stack != []:
        str = stack.pop()
        db(('pop', str))
        if len(str) < len(S):
            for w in words:
                stack.append(str+w)
        elif len(str) == len(S) and str == S:
            return True
    return False


# 逆方向から探す
def solve3():
    string = S + ' '
    n = len(string)
    while n > 1:
        for w in words:
            db((string.rfind(w, 0, n),len(w),n))
            if string.rfind(w, 0, n) + len(w) + 1 == n:
                break
        else:
            return False
        db((n,w))
        n -= len(w)
    return True


debug = False
words = ('dream', 'dreamer', 'erase', 'eraser')
S = input()
db(S)
if solve3():
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

T = int(input())
dct ={}
for z in range(T):
    s = list(input())
    s.sort()
    s = "".join(s)
    if s in dct.keys():
        dct[s] += 1
    else:
        dct[s] = 1
v = 0
for elem in dct.values():
    v += (elem*(elem-1))//2
print(v)

### FIXED CODE ###

T = int(input())
dct ={}
for z in range(T):
    s = "".join(sorted(input()))
    if s in dct:
        dct[s] += 1
    else:
        dct[s] = 1
v = 0
for elem in dct.values():
    v += (elem*(elem-1))//2
print(v)
### BUGGY CODE ###

n,k,*l=map(int,open(0).read().split())
for _ in range(k):
  s=[0]*(n+1)
  for i in range(n):
    s[max(i-l[i],0)]+=1
    s[min(i+l[i]+1,n)]-=1
  for i in range(n):
    s[i+1]+=s[i]
  s.pop()
  if s==l: break
  l=s
print(*l)

### FIXED CODE ###

n,k,*l=map(int,open(0).read().split())
for _ in range(min(k,99)):
  s=[0]*(n+1)
  for i in range(n):
    s[max(i-l[i],0)]+=1
    s[min(i+l[i]+1,n)]-=1
  l[0]=min(s[0],n)
  for i in range(1,n):
    l[i]=min(l[i-1]+s[i],n)
print(*l)
### BUGGY CODE ###

n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))
r = []
idx = 0
cnt = 0
for i in range(n):
    w = a[idx]
    cnt += 1
    if w in r:
        cnt = -1
        break
    elif w == 2:
        break
    elif i == n - 1:
        cnt = -1
        break
    else:
        r.append(w)
        idx = w - 1
print(cnt)

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
cnt = idx = 0
for i in range(n):
    cnt += 1
    if a[idx] == 2:
        break
    if a[a[idx] - 1] == idx + 1:
        cnt = -1
        break
    if i == n - 1:
        cnt = -1
        break
    idx = a[idx] - 1
print(cnt)
### BUGGY CODE ###

n = int(input())
lst = [(bin(i)[2:]).zfill(n) for i in range(2**n)]
num_list = []
A_list = []
xy_list = []
for i in range(n):
    a = int(input())
    A_list.append(a)
    for j in range(a):
        x,y = map(int,input().split())
        xy_list.append([x,y])
for i in range(len(lst)):
    choose = lst[i]
    one_count = choose.count("1")
    a_count = 0
    flag = True
    for num, j in enumerate(A_list):
        a_count += j
        for k in range(a_count-j, a_count):
            x,y = xy_list[k][0],xy_list[k][1]
            if choose[num] == "1" and choose[x-1] != str(y):
                flag = False
    if flag:
        num_list.append(one_count)
    else:
        num_list.append(0)
print(max(num_list))


### FIXED CODE ###

n = int(input())
lst = [(bin(i)[2:]).zfill(n) for i in range(2**n)]
num_list = []
A_list = []
xy_list = []
for i in range(n):
    a = int(input())
    A_list.append(a)
    for j in range(a):
        x,y = map(int,input().split())
        xy_list.append([x,y])
for i in range(len(lst)):
    choose = lst[i]
    one_count = choose.count("1")
    a_count = 0
    flag = True
    for num, j in enumerate(A_list):
        a_count += j
        for k in range(a_count-j, a_count):
            x,y = xy_list[k][0],xy_list[k][1]
            if choose[num] == "1" and choose[x-1] != str(y):
                flag = False
                break
    if flag:
        num_list.append(one_count)
    else:
        num_list.append(0)
print(max(num_list))
### BUGGY CODE ###

#!/usr/bin/env python3


def main():
    N, M = map(int, input().split())
    ans = 0
    for i in range(1,M+1):
        if M%i==0:
            if M//i >= N:
                ans = i
                # print(ans)
            else:
                break
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
from bisect import bisect_left
from heapq import heappush

def cal_divisors(N):
    divisors = []
    i = 1
    while i*i <= N:
        if N % i == 0:
            divisors.append(i)
            if i != N // i:
                divisors.append(N//i)
        i += 1
    divisors.sort()
    return divisors

def main():
    N, M = map(int, input().split())
    ans = cal_divisors(M)
    # print(ans)
    i = bisect_left(ans,N)
    print(M//ans[i])

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

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

for _ in range(0, M, 1):
	A[A.index(max(A))] >>= 1

print(sum(A))

### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A = list(map(lambda o: -int(o), input().split()))
heapq.heapify(A)

for i in range(0, M, 1):
	heapq.heappush(A, -(-heapq.heappop(A) >> 1))

print(-sum(A))
### BUGGY CODE ###

from math import factorial
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse = True)
MOD = 10**9+7
ans = 0
for i in range(n):
  if n-i < k:
    continue
  C =  factorial(n-i-1)//(factorial(k-1)*factorial(n-i-k))
  C %= MOD
  ans += ((a[i]-a[n-i-1]) * C) % MOD
  ans %= MOD

print(ans)
  

### FIXED CODE ###

MAX = 100000 #階乗のmodを求めたい中で最大のもの
MOD = 10**9+7

fac = [0]*MAX   #階乗のmod
inv = [0]*MAX    #その数の逆元
finv = [0]*MAX   #階乗の逆元

def COMinit():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2,MAX):
        fac[i] = (fac[i-1] * i) % MOD
        inv[i] = MOD-(inv[MOD%i] * (MOD//i))%MOD
        finv[i] = (finv[i-1]*inv[i]) %MOD
        
    
def COM(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return (fac[n] * (finv[k]*finv[n-k]))%MOD

#pが素数でないと使えない
COMinit()
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse = True)
MOD = 10**9+7
ans = 0
for i in range(n):
  if n-i < k:
    continue
  C = COM(n-i-1,k-1)
  ans += ((a[i]-a[n-i-1]) * C) % MOD
  ans %= MOD

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

import sys

input = sys.stdin.readline


def binary_search(a, key, low, high):
    ok = low
    ng = high
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if a[mid] < key:
            ok = mid
        else:
            ng = mid
    return ok


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

    L.sort()
    ans = 0
    for a in range(N - 2):
        for b in range(a + 1, N - 1):
            x = binary_search(L, L[a] + L[b], low=0, high=N)
            ans += (x - b)

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from bisect import bisect_left

input = sys.stdin.readline


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

    L.sort()
    ans = 0
    for i in range(N - 1):
        a = L[i]
        for j in range(i + 1, N):
            k = bisect_left(L, a + L[j])
            ans += (k - 1 - j)

    print(ans)


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

import numpy as np
N=int(input())
PP=np.array(input().split(),dtype=np.int64)
count=1
if (N==1):
    print(count)
else:
    for i in range(1,N):
        P1=PP[0:i+1]
        MIN=np.min(P1)
        TAR=P1[i]
        if (MIN==TAR):
            count += 1

    print(count)

### FIXED CODE ###

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

n = int(readline())
p = list(map(int, readline().split()))
temp = p[0]
lis = p[1:]
ans = 1

for i in lis:
    if (i > temp):
        pass
    else:
        temp = i
        ans += 1

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

import itertools
import math
from functools import reduce
def gcd_list(numbers):
    return reduce(math.gcd,numbers)

ans=0
K=int(input())
x=list(itertools.product(range(1,K+1),repeat=3))
for i in x:
    ans+=gcd_list(i)
print(ans)

### FIXED CODE ###

import itertools
import math
from functools import reduce
K=int(input())
ans=0
for i in range(1,K+1):
  for j in range(1,K+1):
    t=math.gcd(i,j)
    for k in range(1,K+1):
      ans+=math.gcd(t,k)
print(ans)
### BUGGY CODE ###

S = list(input())
num_query = int(input())

for i in range(num_query):
    query = input().split()
    if len(query) == 1:
        S = S[::-1]
    else:
        if query[1] == "1":
            S.insert(0, query[2])
        else:
            S.append(query[2])

print("".join(S))


### FIXED CODE ###

S = input()
num_query = int(input())

rev_flag = False
head = []
tail = []
for i in range(num_query):
    query = input().split()
    if len(query) == 1:
        if rev_flag == True:
            rev_flag = False
        else:
            rev_flag = True
    else:
        if rev_flag == False:
            if query[1] == "1":
                head.append(query[2])
            else:
                tail.append(query[2])
        else:
            if query[1] == "1":
                tail.append(query[2])
            else:
                head.append(query[2])

head = "".join(head)
head = head[::-1]
tail = "".join(tail)
ans = head + S + tail

if rev_flag == True:
    ans = ans[::-1]

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

n,k = map(int,input().split())
p = list(map(int,input().split()))
ep = list(map(lambda x:(x+1)/2,p))
m = -1
for i in range(n-k+1):
  if (sum(ep[i:i+k])>m):
    m = sum(ep[i:i+k])
print(m)

### FIXED CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
ep = list(map(lambda x:(x+1)/2,p))
m = -1
epp = [0 for i in range(n+1)]
for i in range(n):
  epp[i+1] = ep[i]+epp[i]
for i in range(n-k+1):
  if (epp[i+k]-epp[i]>m):
    m = epp[i+k]-epp[i]
print(m)
### BUGGY CODE ###

N = int(input())
A = []*N
A[:] = map(int,input().split())

S = ""
for i in range(N):
  S += str(A.index(i+1)+1)
  if i != N:
    S += " "
  
print(S)

### FIXED CODE ###

N = int(input())
A = []*N
A[:] = map(int,input().split())

S = [' ']*N

for i in range(N):
  S[A[i]-1] = str(i+1)

print(" ".join(S))
### BUGGY CODE ###

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

def abc162d(n, s):

    r_arr = []
    g_arr = []
    b_arr = []

    for i in range(n):
        if s[i] == 'R':
            r_arr.append(i)
        elif s[i] == 'G':
            g_arr.append(i)
        else: # 'B'
            b_arr.append(i)

    min1_arr = r_arr
    min2_arr = g_arr
    max_arr = b_arr
    if len(r_arr) < len(g_arr) and len(b_arr) < len(g_arr):
        min1_arr = r_arr
        min2_arr = b_arr
        max_arr = g_arr
    elif len(g_arr) < len(r_arr) and len(b_arr) < len(r_arr):
        min1_arr = g_arr
        min2_arr = b_arr
        max_arr = r_arr

    ans = 0
    max_num = len(max_arr)
    for r_i in min1_arr:
        for g_i in min2_arr:
            min_i = r_i
            max_i = g_i
            if g_i < r_i:
                min_i = g_i
                max_i = r_i
            diff = max_i - min_i
            minmin = min_i - diff
            maxmax = max_i + diff
            exists_central = (max_i + min_i) % 2
            central = (max_i + min_i) / 2

            ans += max_num

            if minmin in max_arr:
                ans -= 1
            if maxmax in max_arr:
                ans -= 1
            if exists_central == 0:
                if central in max_arr:
                    ans -= 1

    return ans

###
# main
if(__name__ == '__main__'):
    # input
    n = int(input())
    s = input()
    
    ans = abc162d(n, s)
    
    # output
    print(ans)
# else:
    # do nothing


### FIXED CODE ###

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

def abc162d(n, s):

    r_arr = []
    g_arr = []
    b_arr = []

    for i in range(n):
        if s[i] == 'R':
            r_arr.append(i)
        elif s[i] == 'G':
            g_arr.append(i)
        else: # 'B'
            b_arr.append(i)

    min1_arr = r_arr
    min2_arr = g_arr
    max_arr = b_arr
    if len(r_arr) < len(g_arr) and len(b_arr) < len(g_arr):
        min1_arr = r_arr
        min2_arr = b_arr
        max_arr = g_arr
    elif len(g_arr) < len(r_arr) and len(b_arr) < len(r_arr):
        min1_arr = g_arr
        min2_arr = b_arr
        max_arr = r_arr

    max_dict = dict()
    for elem in max_arr:
        max_dict[elem] = 1

    except_num = 0
    for r_i in min1_arr:
        for g_i in min2_arr:
            min_i = r_i
            max_i = g_i
            if g_i < r_i:
                min_i = g_i
                max_i = r_i
            diff = max_i - min_i
            minmin = min_i - diff
            maxmax = max_i + diff
            exists_central = (max_i + min_i) % 2

            if minmin in max_dict:
                except_num += 1
            if maxmax in max_dict:
                except_num += 1
            if exists_central == 0:
                central = (max_i + min_i) / 2
                if central in max_dict:
                    except_num += 1

    ans = len(r_arr) * len(g_arr) * len(b_arr) - except_num
    return ans

###
# main
if(__name__ == '__main__'):
    # input
    n = int(input())
    s = input()
    
    ans = abc162d(n, s)
    
    # output
    print(ans)
# else:
    # do nothing