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

import sys
from collections import deque
sys.setrecursionlimit(20000000)
input = sys.stdin.readline


def main():
    n, limit = map(int, input().split())
    jobs = [list(map(int, input().split())) for _ in range(n)]

    for j in jobs:
        j.append(True)
        j.append(True)

    money = 0

    available_jobs = []

    for d in range(1, limit+1):

        for j in jobs:
            if j[0] <= d and j[3]:
                available_jobs.append(j)
                j[3] = False

        if available_jobs:
            available_jobs.sort(key=lambda x: x[1], reverse=True)
            for aj in available_jobs:
                if aj[2]:
                    money += aj[1]
                    aj[2] = False
                    break

    print(money)


if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys
from collections import deque, defaultdict
from heapq import heappop, heappush
sys.setrecursionlimit(20000000)
input = sys.stdin.readline


def main():
    n, limit = map(int, input().split())
    
    jobs = defaultdict(deque)

    for _ in range(n):
        d, v = map(int, input().split())
        jobs[d].append(v)

    money = 0
    available_jobs = []

    for d in range(1, limit+1):
        if d in jobs:
            for j in jobs[d]:
                heappush(available_jobs, -j)

        if available_jobs:
            money += -heappop(available_jobs)

    print(money)


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

#! /usr/bin/env python3
# -*- coding: utf-8 -*-
N,M = [int(x) for x in input().split()]
idls =[]
for i in range(N):
    idls.append(i+1)
ans =[]
for i in range (M):
    L,R = [int(x) for x in input().split()]
    iidls = idls[L-1:R]
    ans += iidls

count = 0
for i in range (N):
    a = ans.count(i+1)
    if a == M:
        count+=1

print(count)







### FIXED CODE ###

#! /usr/bin/env python3
# -*- coding: utf-8 -*-
N,M = [int(x) for x in input().split()]
Llist =[]
Rlist =[]
for i in range (M):
    L,R = [int(x) for x in input().split()]
    Llist.append(L)
    Rlist.append(R)
 
lmax = max(Llist)
Rmax = min(Rlist)

if lmax > Rmax:
    print(0)
else:
    print(Rmax-lmax+1)
### BUGGY CODE ###

import heapq
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
S = sum(A)
if S <= K:
    print(0)

else:
    A.sort()
    F.sort(reverse=True)

    r = A[-1]*F[0]

    l = 0

    while(1):
        tmp = (l+r)//2
        k = 0
        for x, y in zip(A, F):
            k += max(0, x - (tmp // y))
        if k > K:
            l = tmp
        else:
            r = tmp

        if l+1 == r:
            print(r)
            exit(0)


### FIXED CODE ###

import sys
import bisect
import math
input = sys.stdin.readline
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))

A.sort()
F.sort(reverse=True)

B = [(A[i]*F[i], F[i]) for i in range(N)]
B.sort(reverse=True)
L = 0
R = B[0][0]
if sum(A) <= K:
    print(0)
    exit(0)
while(1):
    ans = (L+R) // 2
    flag = True
    tmp = 0
    for i in range(N):
        tmp += math.ceil(max(B[i][0] - ans, 0) / B[i][1])
        if tmp > K:
            flag = False
            break
    if flag:
        R = ans
    else:
        L = ans
    if L == R or L+1 == R:
        print(R)
        break
### BUGGY CODE ###

#%%
N, W = [int(i) for i in input().split()]
weight, value = [0] * (N + 1), [0] * (N + 1)
for i in range(1, N + 1):
    weight[i], value[i] = [int(i) for i in input().split()]
#%%
import  numpy as np
dp = np.zeros((N + 1, W + 1))

#%%
for i in range(1, N + 1):
    for j in range(1, W + 1):
        if weight[i] <= j:
            dp[i][j] = max(value[i] + dp[i-1][j - weight[i]], dp[i - 1][j])
        else:
            dp[i][j] = dp[i - 1][j]
print(int(dp[-1][-1]))


### FIXED CODE ###

N, W = [int(i) for i in input().split()]
weight, value = [0] * (N + 1), [0] * (N + 1)
for i in range(1, N + 1):
    weight[i], value[i] = [int(i) for i in input().split()]
#%%
dp = [[0] * (W + 1) for _ in range(N + 1)]

#%%
for i in range(1, N + 1):
    for j in range(1, W + 1):
        if weight[i] <= j:
            dp[i][j] = max(value[i] + dp[i - 1][j - weight[i]], dp[i - 1][j])
        else:
            dp[i][j] = dp[i - 1][j]
print(int(dp[-1][-1]))
### BUGGY CODE ###

def solve(N, A):
    days = 0
    n_games = N * (N-1) / 2
    game_index = [0] * (N+1)
    while n_games > 0:
        n_games_today = 0
        has_game_today = [False] * (N+1)
        for i in range(1, N+1):
            if has_game_today[i]:
                continue
            j = A[i][game_index[i]]
            if j != -1 & A[j][game_index[j]] == i:
                has_game_today[i] = True
                has_game_today[j] = True
        n_games_today = sum(has_game_today) // 2
        for i in range(1, N+1):
            if has_game_today[i]:
                game_index[i] += 1
        if n_games_today > 0:
            days += 1
            n_games -= n_games_today
        else:
            return -1
    return days


def main():
    N = int(input())
    A = list()
    A.append([])
    for i in range(N):
        a = list(map(int, input().strip().split()))
        a += [-1, ]
        A.append(a)
    print(solve(N, A))


if __name__ == "__main__":
    main()


### FIXED CODE ###

def make_state(N):
    state = [[-1 for j in range(N+1)] for i in range(N+1)]
    min_state = 0
    s = min_state
    for i in range(1, N+1):
        for j in range(1, i):
            state[i][j] = s
            state[j][i] = s
            s += 1
    return state


def solve(N, A):
    state = make_state(N)
    max_state = N * (N-1) // 2
    n_prev_states = [0 for i in range(max_state)]
    next_states = [set() for i in range(max_state)]
    for i in range(1, N+1):
        for k in range(N-2):
            ps = state[i][A[i][k]]
            ns = state[i][A[i][k+1]]
            n_prev_states[ns] += 1
            next_states[ps].add(ns)
    
    today_states = set()
    for s in range(max_state):
        if n_prev_states[s] == 0:
            today_states.add(s)
    
    n_days = 0
    n_states_left = max_state
    while len(today_states) > 0:
        n_days += 1
        if len(today_states) == 0:
            break
        n_states_left -= len(today_states)
        nextday_states = set()
        for s in today_states:
            for ns in next_states[s]:
                n_prev_states[ns] -= 1
                if n_prev_states[ns] == 0:
                    nextday_states.add(ns)
        today_states = nextday_states
    return n_days if n_states_left == 0 else -1


def main():
    N = int(input())
    A = list()
    A.append([])
    for i in range(N):
        a = list(map(int, input().strip().split()))
        A.append(a)
    print(solve(N, A))


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

#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin
from heapq import heappush, heappop


def main():
  ## input
  N,Q = map(int, stdin.readline().rstrip().split())
  STX = [[0,0,0] for _ in range(N)]
  for i in range(N):
    s,t,x = map(int, stdin.readline().rstrip().split())
    STX[i] = [x,s-x,t-x]
  Dn = [int(stdin.readline().rstrip()) for _ in range(Q)] + [10**10]
  ans = []
  STX=sorted(STX)
  
  for x,s,t in STX:
    l = bisect_left(Dn,s)
    r = l
    while Dn[r] < t:
      heappush(ans, (Dn[r],x))
      r += 1
    del Dn[l:r]

  for d in Dn[:-1]:
    heappush(ans, (d,-1))

  return ans


if __name__ == "__main__":
  ans = main()
  while len(ans) > 0:
    print(heappop(ans)[1])    


### FIXED CODE ###

import sys
from bisect import bisect_left



N,Q = map(int, input().split())
lines = sys.stdin.readlines()
kkk = []
for line in lines[:N]:
  s, t, x = map(int, line.split())
  kkk.append((x, s, t))
kkk.sort()
ddd = list(map(int, lines[N:]))

ans = [-1] * Q
skip = [-1] * Q
for x, s, t in kkk:
  ss = bisect_left(ddd, s - x)
  tt = bisect_left(ddd, t - x)
  while ss < tt:
    sk = skip[ss]
    if sk == -1:
      ans[ss] = x
      skip[ss] = tt
      ss += 1
    else:
      ss = sk

print('\n'.join(map(str, ans)))
### BUGGY CODE ###

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

for i in range(a):
    for j in range(a):
        if(j == i): continue
        if(A[i]%A[j] == 0):
            d_num -= 1
            break
print(d_num)


### FIXED CODE ###

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

ndiv_sum = 0
max_num = A[-1]
no_div = [True] * (max_num+1)
for i in range(len(A)-1):
    if no_div[A[i]]:
        for j in range(A[i], max_num+1, A[i]):
            no_div[j] = False
        if A[i]!=A[i+1]:
            ndiv_sum += 1
if no_div[A[-1]]:
    ndiv_sum += 1
print(ndiv_sum)
### BUGGY CODE ###

dbg = False

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

if a > b:
    x, y = a, b
else:
    x, y = b, a

for i in range(1, y+1):
    if y % i == 0:
        gcd_tmp = int(y / i)
        if dbg: print(gcd_tmp)
        if x % gcd_tmp == 0:
            gcd = gcd_tmp
            break

print(gcd)

### FIXED CODE ###

dbg = False

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

if a > b:
    x, y = a, b
else:
    x, y = b, a

divs = [1]
for i in range(1, int((y+1)/2)+1):
    gcd_tmp = int(y / i)
    if dbg: print('%d, %d' % (i, gcd_tmp))
    if i > gcd_tmp:
        break
    if y % i == 0:
        if x % gcd_tmp == 0:
            print(gcd_tmp)
            exit()
        elif x % i == 0:
            divs.append(i)

print(max(divs))
### BUGGY CODE ###

N,A,B=map(int,input().split())
ans=0
for i in range(N):
    if (i+1)%(A+B)<=A and (i+1)%(A+B)!=0:
        ans+=1
print(ans)

### FIXED CODE ###

N,A,B=map(int,input().split())
t=N//(A+B)
ans=(t*A)+(min((N%(A+B)),A))
print(ans)
### BUGGY CODE ###

from operator import itemgetter
n, m = map(int, input().split())
bridge = [True] * (n-1)  
ab = []
for _ in range(m):
  a, b = map(int, input().split())
  ab.append((a,b))
ab = sorted(ab, key=itemgetter(1))
count = 0
for a, b in ab:
  if all(bridge[a-1:a-1 + (b-a)]):
    bridge[b-2] = False
    count += 1
print(count)


### FIXED CODE ###

from operator import itemgetter
n, m = map(int, input().split())
bridge = 0
ab = []
for _ in range(m):
  a, b = map(int, input().split())
  ab.append((a,b))
ab = sorted(ab, key=itemgetter(1))
count = 0
for a, b in ab:
  if not a <= bridge <= b:
    count += 1
    bridge = b-1
print(count)
### BUGGY CODE ###

import math
import time
start=time.time()
K=int(input())
ans=0
if K%2==0:
    print(-1)
else:
    if K%7==0:
        K//=7
    k=1
    kk=1
    end=time.time()
    while True:
        if (end-start)>1.5:
            ans=-1
            break
        kk*=10
        kk%=9*K
        if kk==1:
            ans=k
            break
        else:
            k+=1


    print(ans)




### FIXED CODE ###

import math
import time
start=time.time()
K=int(input())
ans=0
if K%2==0:
    print(-1)
else:
    if K%7==0:
        K//=7
    k=1
    kk=1
    while True:
        now=time.time()
        if (now-start)>1.8:
            ans=-1
            break
        kk*=10
        kk%=9*K
        if kk==1:
            ans=k
            break
        else:
            k+=1


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

import bisect

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

a.sort()
b.sort()
c.sort()

ans = 0
for l in a:
    m_idx = bisect.bisect_right(b, l)
    if m_idx == n:
        break
    for m in b[m_idx:]:
        l_idx = bisect.bisect_right(c, m)
        if l_idx == n:
            break
        ans += n - l_idx

print(ans)


### FIXED CODE ###

import bisect

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

a.sort()
b.sort()
c.sort()


def binary_upper(k, x):
    return len(k) - bisect.bisect_right(k, x)


def binary_lower(k, x):
    return bisect.bisect_left(k, x)


ans = 0

for middle in b:
    cnt_a = binary_lower(a, middle)
    cnt_c = binary_upper(c, middle)
    ans += cnt_a * cnt_c

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

N=int(input())
L=list(map(int,input().split()))
s=[(i+1)+L[i] for i in range(N)]
d=[(i+1)-L[i] for i in range(N)]
ans=0
for i in range(N):
  for j in range(N):
    if i==j:
      continue
    if s[i]==d[j]:
      ans+=1
print(ans)

### FIXED CODE ###

from collections import Counter
N=int(input())
L=list(map(int,input().split()))
s=[(i+1)+L[i] for i in range(N)]
s=Counter(s)
d=[(i+1)-L[i] for i in range(N)]
d=Counter(d)
ans=0
for i in s:
  if i in d:
    ans+=s[i]*d[i]
print(ans)
### BUGGY CODE ###

import heapq
#これを加える！！！！
def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt

n = int(input())
works = [[]] * n
for i in range(n):
  a, b = map(int, input().split(' '))
  works[i] = [a, b]

ans = 'Yes'
sorted_works = sorted(works, key=lambda x: x[1], reverse=True)
max_deadline = sorted_works[0][1]
# print('max_deadline', max_deadline)
h = []
deadline_i = 0
work_day = max_deadline # 作業日
# 締め切り最終日から0日に向かってループ
for d in range(max_deadline, -1, -1):
  # その日が締め切りの作業時間を優先度キューに追加
  for i in range(deadline_i, n):
    work_time, deadline = sorted_works[i]
    if deadline == d:
      _heappush_max(h, work_time)
      deadline_i += 1
    else:
      break
  # 作業ができない日であれば、次のループへ
  if d > work_day:
    continue
  
  # 作業ができる日
  
  # 作業がなければ次のループへ
  if len(h) == 0:
    continue
  
  
  # その日に終了しても良い作業の中で時間が最長の作業時間を取得
  max_work_time = _heappop_max(h)
  # 次の作業日を設定
  work_day = d - max_work_time
  
  # 0日より前になる = 作業量が多いので実行不可
  if work_day < 0:
    ans = 'No'
  
  

print(ans)
# print(works)
# print(sorted_works)

### FIXED CODE ###

n = int(input())
works = [[]] * n
for i in range(n):
  a, b = map(int, input().split(' ')) # a = 時間, b = 締め切り
  works[i] = [a, b]

ans = 'Yes'
sorted_works = sorted(works, key=lambda x: x[1]) # 締切の早い順にソート
total = 0

for work in sorted_works:
  total += work[0]
  if total > work[1]:
    ans = 'No'
    break
  
print(ans)
### BUGGY CODE ###

S=input()

T,A=[1]+[0]*2018,0
for i in range(1,len(S)+1):
  T[int(S[-i:])%2019]+=1
print(sum(T[i]*~-T[i]//2 for i in range(2019)))


### FIXED CODE ###

S=input()
C,m,T=2019,0,[1]+[0]*2018
for i,s in enumerate(S[::-1]):
  m=(m+int(s)*pow(10,i,C))%C
  T[m]+=1
print(sum(T[i]*~-T[i]//2 for i in range(2019)))
### BUGGY CODE ###

N = int(input())
S_list = []
S_count_list = []
S_set = set()

for n in range(N):
    s = input()

    if s in S_set:
        index_s = S_list.index(s)
        S_count_list[index_s] += 1
    
    else:
        S_set.add(s)
        S_list.append(s)
        S_count_list.append(1)

max_list = [i for i, v in enumerate(S_count_list) if v == max(S_count_list)]

max_S_list = []
for i in max_list:
    max_S_list.append(S_list[i])

max_S_list.sort()

for ans_s in max_S_list:
    print(ans_s)


### FIXED CODE ###

N = int(input())
S_dic = {}

for n in range(N):
    S = input()

    if S in S_dic:
        S_dic[S] += 1
    else:
        S_dic[S] = 1


# 最大のvalueを取得する
max_value = max(S_dic.values())

max_S_list = [k for k, v in S_dic.items() if v == max_value]
max_S_list = sorted(max_S_list)

for max_S in max_S_list:
    print(max_S)
### BUGGY CODE ###

from collections import Counter, defaultdict

n, m = map(int, input().split())
ab = sorted([list(map(int, input().split())) for i in range(n)])
c = [[]] * m
a, b = ab[0]
last = a
ad = [b]
for i in range(1, n):
    a, b = ab[i]
    if a == last:
        ad.append(b)
    else:
        if last <= m:
            c[last - 1] = ad
        ad = [b]
    last = a
if a <= m:
    c[a - 1] = ad
choice = defaultdict(int)
ans = 0
for i in range(m):
    for k, v in Counter(c[i]).items():
        choice[k] += v
    if choice:
        use = max(choice)
        ans += use
        choice[use] -= 1
        if choice[use] <= 0:
            del choice[use]
print(ans)

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
ab = sorted([list(map(int, input().split())) for i in range(n)])
c = [[]] * m
a, b = ab[0]
last = a
ad = [b]
for i in range(1, n):
    a, b = ab[i]
    if a == last:
        ad.append(b)
    else:
        if last <= m:
            c[last - 1] = ad
        ad = [b]
    last = a
if a <= m:
    c[a - 1] = ad
a = [3, 0, 2, 6]
choice = []
heapq.heapify(choice)
ans = 0
for i in range(m):
    for j in c[i]:
        heapq.heappush(choice, -j)
    if choice:
        ans -= heapq.heappop(choice)
print(ans)
### BUGGY CODE ###

def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline

    N, L = map(int, input().split())
    dic = defaultdict(int)
    for _ in range(N):
        s = input().rstrip('\n')
        s = [si for si in s]
        for i in range(len(s)):
            dic[''.join(s[:i+1])] = 1

    g = 0
    key = list(dic.keys())
    for s in key:
        t = [si for si in s]
        t[-1] = '0' if t[-1] == '1' else '1'
        t = ''.join(t)
        if not dic[t]:
            tmp = L - len(s) + 1
            cnt = 0
            while tmp % 2 == 0:
                tmp //= 2
                cnt += 1
            g ^= (2**cnt)

    if g:
        print('Alice')
    else:
        print('Bob')


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline

    mod = 10**10+7
    mod2 = 10**10+9
    mod3 = 998244353
    N, L = map(int, input().split())
    dic = defaultdict(int)
    dic2 = defaultdict(int)
    dic3 = defaultdict(int)
    h_list = []
    h2_list = []
    h3_list = []
    pair = {}
    pair2 = {}
    pair3 = {}
    M = 0
    for _ in range(N):
        s = input().rstrip('\n')
        h = 0
        h2 = 0
        h3 = 0
        for i in range(len(s)):
            M += 1
            h = (h*1007 + int(s[i]) + 1) % mod
            pair[h] = (h + 1)%mod if s[i] == '0' else (h-1)%mod
            h2 = (h2 * 2009 + int(s[i]) + 1) % mod2
            pair2[h2] = (h2 + 1)%mod2 if s[i] == '0' else (h2-1)%mod2
            h3 = (h3 * 3001 + int(s[i]) + 1) % mod3
            pair3[h3] = (h3 + 1) % mod3 if s[i] == '0' else (h3 - 1) % mod3
            dic[h] = i+1
            dic2[h2] = i+1
            dic[h3] = i+1
            h_list.append(h)
            h2_list.append(h2)
            h3_list.append(h3)

    g = 0
    seen = defaultdict(int)
    seen2 = defaultdict(int)
    seen3 = defaultdict(int)
    for i in range(M):
        s, s2, s3 = h_list[i], h2_list[i], h3_list[i]
        if seen[s] and seen2[s2] and seen3[s3]:
            continue
        t = pair[s]
        t2 = pair2[s2]
        t3 = pair3[s3]
        if dic[t] == 0 or dic2[t2] == 0 or dic3[t3] == 0:
            p = [dic[s], dic2[s2], dic3[s3]]
            p.sort()
            tmp = L - p[1] + 1
            '''
            if not seen[s]:
                tmp = L - dic[s] + 1
            elif not seen[s2]:
                tmp = L - dic2[s2] + 1
            else:
                tmp = L - dic3[s3] + 1
            '''
            cnt = 0
            while tmp % 2 == 0:
                tmp //= 2
                cnt += 1
            g ^= (2**cnt)
            #print(g, s, s2, t, t2, dic[t], dic2[t2])
        seen[s] = 1
        seen2[s2] = 1
        seen3[s3] = 1

    if g:
        print('Alice')
    else:
        print('Bob')


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

n=int(input())
d=0

for i in range(1,n+1):

    a=i
    b=(n//i)*i
    c=b//i -a//i+1
    d+=(c*(a+b))//2

    

print(d)


### FIXED CODE ###

n=int(input())
#n=10000000
ksum=0
for k in range(1,n+1):
    m=n//k
    ksum+=k*m*(m+1)//2
    
print(ksum)
### BUGGY CODE ###

x = int(input())
result = 0
ary = list(map(int,input().split()))
miss = False
i = 1
while(True):
  if (i not in ary):
    if (i == 1):
      miss = True
    break
  b = ary.index(i)
  i += 1
  ary = ary[b+1:]

if miss:
  print(-1)
else:
  print(x - i + 1)
    

### FIXED CODE ###

x = int(input())
result = 0
ary = list(map(int,input().split()))
miss = False
res = 1
for i in range(x):
  if (res == ary[i]):
    res += 1
print(-1 if res-1 == 0 else x - res + 1)
### BUGGY CODE ###

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

point = 0
rList = []
gList = []
bList = []
for value in s:
    point += 1
    if value == "R":
        rList.append(point)
    elif value == "G":
        gList.append(point)
    elif value == "B":
        bList.append(point)

count = 0
for iIndex, iItem in enumerate(rList):
    for jIndex, jItem in enumerate(gList):
        for kIndex, kItem in enumerate(bList):
            if (jItem - iItem != kItem - jItem) and iItem < jItem < kItem:
                count += 1
for iIndex, iItem in enumerate(rList):
    for jIndex, jItem in enumerate(bList):
        for kIndex, kItem in enumerate(gList):
            if (jItem - iItem != kItem - jItem) and iItem < jItem < kItem:
                count += 1
for iIndex, iItem in enumerate(gList):
    for jIndex, jItem in enumerate(bList):
        for kIndex, kItem in enumerate(rList):
            if (jItem - iItem != kItem - jItem) and iItem < jItem < kItem:
                count += 1
for iIndex, iItem in enumerate(gList):
    for jIndex, jItem in enumerate(rList):
        for kIndex, kItem in enumerate(bList):
            if (jItem - iItem != kItem - jItem) and iItem < jItem < kItem:
                count += 1
for iIndex, iItem in enumerate(bList):
    for jIndex, jItem in enumerate(rList):
        for kIndex, kItem in enumerate(gList):
            if (jItem - iItem != kItem - jItem) and iItem < jItem < kItem:
                count += 1
for iIndex, iItem in enumerate(bList):
    for jIndex, jItem in enumerate(gList):
        for kIndex, kItem in enumerate(rList):
            if (jItem - iItem != kItem - jItem) and iItem < jItem < kItem:
                count += 1
print(count)

### FIXED CODE ###

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

point = 0
rList = []
gList = []
bList = []
for value in s:
    point += 1
    if value == "R":
        rList.append(point)
    elif value == "G":
        gList.append(point)
    elif value == "B":
        bList.append(point)

if len(rList) < 1 or len(gList) < 1 or len(bList) < 1:
    print(0)
else:
    count = len(rList) * len(gList) * len(bList)
    for i in range(n-1):
        for j in range(i+1,n):
            k = 2*j-i
            if k < n and s[i] != s[j] and s[i] != s[k] and s[j] != s[k]:
                count -= 1
    print(count)