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

n,m = map(int, input().split())
l = [tuple(map(int, input().split())) for _ in range(m)]
l.sort(key=lambda x:x[1],reverse = True)
dec = 0
while l:
  a = l.pop()
  dec += 1
  l = [i for i in l if not (i[0] < a[1] <= i[1])]
print(dec)

### FIXED CODE ###

n,m = map(int, input().split())
l = [tuple(map(int, input().split())) for _ in range(m)]
l.sort(key=lambda x:x[1])
dec = 0
cur = 0
for i in l:
  if i[0] < cur <= i[1]:
    continue
  else:
    dec += 1
    cur = i[1]
print(dec)
### BUGGY CODE ###

s = str(input())
l = len(s)
s = s[::-1]
i = 0
while i < l:
    if s[i] == "r":
        if (s[i:min(l,i+7)] == "remaerd"):
            i += 7
        elif (s[i:min(l,i+6)] == "resare"):
            i += 6
        else:
            print('NO')
            break
    
    elif s[i] == "m":
        if (s[i:min(l,i+5)] == "maerd"):
            i += 5
        else:
            print('NO')
            break
            
    elif s[i] == "e":
        if (s[i:min(l,i+5)] == "esare"):
            i + 5
        else:
            print('NO')
            break
            
    else:
        print('NO')
        break
        
    
else:
    print('YES')

### FIXED CODE ###

s = str(input())
l = len(s)
s = s[::-1]
i = 0
while i < l:
    if s[i] == "r":
        if (s[i:min(l,i+7)] == "remaerd"):
            i += 7
        elif (s[i:min(l,i+6)] == "resare"):
            i += 6
        else:
            print('NO')
            break
    
    elif s[i] == "m":
        if (s[i:min(l,i+5)] == "maerd"):
            i += 5
        else:
            print('NO')
            break
            
    elif s[i] == "e":
        if (s[i:min(l,i+5)] == "esare"):
            i += 5
        else:
            print('NO')
            break
            
    else:
        print('NO')
        break
        
    
else:
    print('YES')
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)


def gcd(a, b):
    if a == 0:
        return b
    return gcd(b % a, a)


def xgcd(a):
    size = len(a)
    if size == 1:
        return a[0]
    if size == 2:
        return gcd(a[0], a[1])

    la = a[:size // 2]
    ra = a[size // 2:]

    return gcd(xgcd(la), xgcd(ra))


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


ans = 0
for i in range(n):
    tmp = a[i]
    a[i] = a[i - 1]
    ans = max(ans, xgcd(a))
    a[i] = tmp

print(ans)

### FIXED CODE ###

def gcd(a, b):
    if a == 0:
        return b
    if b == 0:
        return a
    return gcd(b % a, a)


n = int(input())
a = list(map(int, input().split()))
b = [0] * (n + 1)
c = [0] * (n + 1)

for i in range(n):
    b[i + 1] = gcd(b[i], a[i])
    c[i + 1] = gcd(c[i], a[-i - 1])

ans = 0
for i in range(n):
    ans = max(ans, gcd(b[i], c[n - i - 1]))

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

import math
K = int(input())

ans = 0
for c in range(1, K+1):
    for b in range(1, K+1):
        for a in range(1, K+1):
            ans += math.gcd(math.gcd(a, b), c)
print(ans)

### FIXED CODE ###

import math
K = int(input())

ans = 0
ab = []
for b in range(1, K+1):
    for a in range(1, K+1):
        ab.append(math.gcd(a, b))
        
for c in range(1, K+1):
    for i in ab:
        ans += math.gcd(c, i)
print(ans)
### BUGGY CODE ###

def solve(string):
    n = len(string)
    q_pos = [i for i in range(n) if string[n - i - 1] == "?"]
    table = [[0] * 13 for _ in range(2)]
    table[0][int(string.replace("?", "0")) % 13] = 1
    for i in range(len(q_pos)):
        base = pow(10, q_pos[i], 13)
        for j in range(13):
            for k in range(10):
                table[1][(j + k * base) % 13] += table[0][j]
        for j in range(13):
            table[1][j] %= (10**9 + 7)
        table[0] = table[1]
        table[1] = [0] * 13
    return str(table[0][5])


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


### FIXED CODE ###

def solve(string):
    n = len(string)
    q_pos = [i for i in range(n) if string[n - i - 1] == "?"]
    table = [[0] * 13 for _ in range(2)]
    table[0][int(string.replace("?", "0")) % 13] = 1
    for i in range(len(q_pos)):
        base = pow(10, q_pos[i], 13)
        for j in range(13):
            for k in range(10):
                table[1][(j + k * base) % 13] += table[0][j]
        for j in range(13):
            table[1][j] %= (10**9 + 7)
        table[0] = table[1]
        table[1] = [0] * 13
    return str(table[0][5])


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

import numpy as np

n, d, a = map(int, input().split())
monster = []
for _ in range(n):
  x, h = map(int, input().split())
  monster.append([x, h])
monster.sort()
monster = np.array(monster)
bomb = 0
j = 1
for i in range(n):
  while j < n and monster[j][0] - monster[i][0] <= 2 * d:
    j += 1
  if monster[i][1] <= 0:
    continue
  b = (monster[i][1] - 1) // a + 1
  atk = a * b
  bomb += b
  monster[i+1:j, 1] -= atk
print(bomb)

### FIXED CODE ###

import heapq
from collections import deque

n, d, a = map(int, input().split())
monster = []
for _ in range(n):
  x, h = map(int, input().split())
  heapq.heappush(monster, (x, h))
bomb = 0
damage = 0
queue = deque()
while monster:
  x, h = heapq.heappop(monster)
  while True:
    if queue and x > queue[0][0]:
      damage -= queue.popleft()[1]
    else:
      break
  h -= damage
  if h <= 0:
    continue
  b = (h - 1) // a + 1
  bomb += b
  queue.append((x + 2 * d, a * b))
  damage += a * b
print(bomb)
### BUGGY CODE ###

#coding:utf-8



def main():
    
    def dbg(*something):
        if DEBUG:
            print(*something)


    #正の宝石を戻すことはない
    #負の宝石を戻すのは後半
    from sys import stdin
    from math import ceil,floor
    DEBUG = False
    N,K = list(map(int,stdin.readline().split()))
    V = list(map(int,stdin.readline().split()))


    #残りk回のとき深さk以下の場所に正の宝石がない→終了
    #i回の操作で取れる石>それまでにとるi-1個の石の和
    #深さiにある石vの価値：v - (それまでにとるi-1個の石の和　except (k-i)個の負の石)
    '''
    '''




    def tansaku(left,right,rK,N,score):
        dbg(V[left:right+1],rK,N,score)

        N.sort()
        # max_v = score + sum(N[rK:])
        max_v = score
        for i in range(rK,len(N)):
            max_v += N[i]
        


        # n = []
        for i in range(left,min(rK+left, ceil((right - left +1)/2)+left)):
            
            if V[i] <= 0:
                continue


            next_rK = rK - 1 - (i - left)
            next_tmp_v = tansaku(i+1,right,  next_rK, N+V[left:i], score+V[i])
            #max_v = max(next_tmp_v , max_v)
            if max_v < next_tmp_v:
                max_v = next_tmp_v


            break

        # n = []
        for i in range(right ,max(right - ceil((right-left+1)/2)  ,right-rK)  ,-1 ):
            
            if V[i] <= 0:
                continue

            next_rK = rK - 1 - (right - i)
            next_tmp_v = tansaku(   left,   i-1  ,next_rK,N+V[i+1:right+1],score+V[i])
            #max_v = max(next_tmp_v , max_v)
            if max_v < next_tmp_v:
                max_v = next_tmp_v
            break


        return max_v

    print(tansaku(0,len(V)-1,K,[],0))





if __name__ == '__main__':
    main()


### FIXED CODE ###

#coding:utf-8



def main():
    
    def dbg(*something):
        if DEBUG:
            print(*something)


    #正の宝石を戻すことはない
    #負の宝石を戻すのは後半
    from sys import stdin
    from math import ceil,floor
    DEBUG = False
    N,K = list(map(int,stdin.readline().split()))
    V = list(map(int,stdin.readline().split()))
    
    max_value = 0
    dbg([i for i in range(3,-1,-1)])
    for getnum in range(1,min(N+1,K+1)):  #取る宝石の総数
        for a in range(getnum + 1):  #左から石を取る回数
            J = [0] * getnum #石
            b = getnum - a #右から石を取る回数
            for i in range(a):
                J[i] = V[i]
            for i in range(b):
                J[a+i] = V[-i-1]
            J.sort()
            #dbg(J,a,b)
            t = min(K-getnum,getnum) #捨てる石
           
            for i in range(t): 
                if J[i] >= 0:
                    t = i
                    break
            #dbg(J,i,t,a,b,J[t:])
            tmp_max = sum(J[t:])

            max_value = max(max_value,tmp_max)
    print(max_value)



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

import bisect
import numpy as np
INF=10**18
A,B,Q=map(int,input().split())
s=[int(input()) for i in range(A)]
t=[int(input()) for i in range(B)]
s=[-INF]+s+[INF]
t=[-INF]+t+[INF]
s=np.array(s)
t=np.array(t)
for q in range(Q):
    X=int(input())
    t1=bisect.bisect_right(t,X)
    s1=bisect.bisect_right(s,X)
    res=INF
    for T in [t[t1],t[t1-1]]:
        for S in [s[s1],s[s1-1]]:
            ans1=abs(X-T)+abs(S-T)
            ans2=abs(X-S)+abs(S-T)
            res=min(res,ans1,ans2)
    print(res)



### FIXED CODE ###

import bisect
INF=10**18
A,B,Q=map(int,input().split())
s=[int(input()) for i in range(A)]
t=[int(input()) for i in range(B)]
s=[-INF]+s+[INF]
t=[-INF]+t+[INF]
for q in range(Q):
    X=int(input())
    t1=bisect.bisect_right(t,X)
    s1=bisect.bisect_right(s,X)
    res=INF
    for T in [t[t1],t[t1-1]]:
        for S in [s[s1],s[s1-1]]:
            ans1=abs(X-T)+abs(S-T)
            ans2=abs(X-S)+abs(S-T)
            res=min(res,ans1,ans2)
    print(res)
### BUGGY CODE ###

n=int(raw_input())
t=a=1

for i in range(n):
    x,y=map(int,raw_input().split())
    if t<=x and a<=y:
        t=x
        a=y
    else:
        tmp=min(t/x,a/y)
        while 1:
            if x*tmp>=t and y*tmp>=a:
                t=x*tmp
                a=y*tmp
                break
            tmp+=1
print t+a
exit()

### FIXED CODE ###

n=int(raw_input())
t=a=1

for i in range(n):
    x,y=map(int,raw_input().split())
    n=max((t+x-1)/x,(a+y-1)/y)
    t=n*x
    a=n*y
print t+a
### BUGGY CODE ###


def calc(n):
    r = 0
    for i in range(1, n):
        r += i
    return r


n = int(input())
r = calc(n)
print(r)


### FIXED CODE ###


def calc(n):
    return (1 + n - 1) * (n-1) // 2


n = int(input())
r = calc(n)
print(r)
### BUGGY CODE ###

N = int(input())
price = list(map(int,input().split()))
start = 1000
for i in range(N-1):
    if price[i]<price[i+1]:
        for j in range(start//price[i]):
            start += price[i+1]-price[i]


print(max(1000,start))

### FIXED CODE ###

N = int(input())
price = list(map(int,input().split()))
start = 1000
for i in range(N-1):
    if price[i]<price[i+1]:
        times = start//price[i]
        start += times*(price[i+1]-price[i])


print(max(1000,start))
### BUGGY CODE ###

N = int(input())

ans = 0
for num in range(N):
    ans += num


print(ans)

### FIXED CODE ###

N = int(input())
a = N - 1
print(int(a*(a+1)//2))
### BUGGY CODE ###

l,r = map(int,input().split())
mod = 2019
li = list(set([i%mod for i in range(l,r+1)]))
li.sort()
ans = 10**9

for left in range(len(li)-1):
    ans = min(min(list(map(lambda x: li[left]*x%mod, li[left+1:]))),ans)
    left +=1
print(ans)

### FIXED CODE ###

import numpy as np
l,r = map(int,input().split())
mod = 2019
arr = np.array(list(set([i%mod for i in range(l,min(r+1,l+2019))])))
ans = 2019

for left in range(len(arr)-1):
    ans = min(min(arr[left]*arr[left+1:]%mod),ans)
    if ans == 0:
        print(ans)
        exit()
print(ans)
### BUGGY CODE ###

mn,jn=map(int,input().split())
mm=input()
mi_mm={}
go=[1 for i in range(mn+2)]
for i in range(mn):
    mi_mm.setdefault(mm[i],[])
    mi_mm[mm[i]]+=[i+1]

for ji in range(jn):
    ju=input().split()
    nk=jn-ji
    if ju[0] in mm[:nk]+mm[-nk:]:
        if ju[1]=="L":
            for mi in mi_mm[ju[0]]:
                go[mi-1]+=go[mi]
                go[mi]=0
        else:
            for mi in mi_mm[ju[0]][::-1]:
                go[mi +1] += go[mi]
                go[mi] = 0

print(sum(go[1:mn+1]))

### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n, q = MI()
    s = SI()
    td = [SI().split() for _ in range(q)]
    ans = n
    # 左に落ちるゴーレムのうち、最右のインデックス
    l = -1
    r = n
    while l + 1 < r:
        m = (l + r) // 2

        def ok(m):
            for t, d in td:
                if s[m] == t: m += (d == "R") * 2 - 1
                if m == -1: return True
                if m == n: return False
            return False

        if ok(m): l = m
        else: r = m
    ans -= l + 1
    # 右に落ちるゴーレムのうち、最左のインデックス
    l = -1
    r = n
    while l + 1 < r:
        m = (l + r) // 2

        def ok(m):
            for t, d in td:
                if s[m] == t: m += (d == "R") * 2 - 1
                if m == -1: return False
                if m == n: return True
            return False

        if ok(m): r = m
        else: l = m
    ans -= n - r

    print(ans)

main()
### BUGGY CODE ###

from itertools import product

X, Y, Z, K = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

candidates = []
for i, j, k in product(range(len(A)), range(len(B)), range(len(C))):
    if i * j * k <= K:
        candidates.append(A[i] + B[j] + C[k])
candidates.sort(reverse=True)

for c in candidates[:K]:
    print(c)

### FIXED CODE ###

from itertools import product

X, Y, Z, K = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

AB = [a + b for a, b in product(A, B)]
AB.sort(reverse=True)

ABC = [ab + c for ab, c in product(AB[:K], C)]
ABC.sort(reverse=True)

for abc in ABC[:K]:
    print(abc)
### BUGGY CODE ###

from collections import deque


def read():
    N, Q = list(map(int, input().strip().split()))
    G = [i for i in range(N+1)]
    PX = list()
    G[1] = 0  # 終点
    for i in range(N-1):
        a, b = list(map(int, input().strip().split()))
        G[b] = a  # 逆辺を張る
    for i in range(Q):
        px = list(map(int, input().strip().split()))
        PX.append(px)
    return N, Q, G, PX


def solve(N, Q, G, PX):
    C = [0 for i in range(N+1)]
    V = [-1 for i in range(N+1)]
    for p, x in PX:
        C[p] += x
    for i in range(N, 0, -1):
        node = i
        v = 0
        while node > 0:
            if V[node] >= 0:  # use cache
                v += V[node]
                break
            v += C[node]
            node = G[node]
        V[i] = v
    return ' '.join(map(str, V[1:]))
    

if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))


### FIXED CODE ###

import sys
sys.setrecursionlimit(200000)
from collections import deque


def read():
    N, Q = list(map(int, input().strip().split()))
    G = [list() for i in range(N+1)]
    PX = list()
    for i in range(N-1):
        a, b = list(map(int, input().strip().split()))
        G[a].append(b)
        G[b].append(a)
    for i in range(Q):
        px = list(map(int, input().strip().split()))
        PX.append(px)
    return N, Q, G, PX


def bfs(parent, G, C, V):
    q = deque()
    q.append(1)
    while len(q) > 0:
        parent = q.pop()
        V[parent] = True
        for child in G[parent]:
            if not V[child]:
                C[child] += C[parent]
                q.append(child)
    

def solve(N, Q, G, PX):
    C = [0 for i in range(N+1)]
    V = [False for i in range(N+1)]
    for p, x in PX:
        C[p] += x
    bfs(1, G, C, V)
    return ' '.join(map(str, C[1:]))
    

if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))
### BUGGY CODE ###

def merge(S,left,right,mid,cnt):
    a = mid - left
    b = right - mid
    L = [0]*(a+1)
    R = [0]*(b+1)
    for i in range(a):
        L[i] = S[left+i]
    for i in range(b):
        R[i] = S[mid+i]
    L[a] = float("inf")
    R[b] = float("inf")
    j = 0
    k = 0
    for i in range(left,right):
        cnt[0] += 1
        if L[j] <= R[k]:
            S[i] = L[j]
            j += 1
        else:
            S[i] = R[k]
            k += 1
            
def mergeSort(S,left,right,cnt):
    if left+1<right:
        mid = (int)((left+right)/2)
        mergeSort(S,left,mid,cnt)
        mergeSort(S,mid,right,cnt)
        merge(S,left,right,mid,cnt)
        
n = int(input())
S = list(map(int, input().split()))
cnt = [0]
cnt[0] = 0
mergeSort(S,0,n,cnt)
print(*S)
print(*cnt)


### FIXED CODE ###

cnt = 0
def merge(S,left,right,mid):
    a = mid - left
    b = right - mid
    L = S[left:left+a]+[float("inf")]
    R = S[mid:mid+b]+[float("inf")]
    j = 0
    k = 0
    for i in range(left,right):
        global cnt
        cnt+=1
        if L[j] <= R[k]:
            S[i] = L[j]
            j += 1
        else:
            S[i] = R[k]
            k += 1
            
def mergeSort(S,left,right):
    if left+1<right:
        mid = (int)((left+right)/2)
        mergeSort(S,left,mid)
        mergeSort(S,mid,right)
        merge(S,left,right,mid)
        
n = int(input())
S = list(map(int, input().split()))
mergeSort(S,0,n)
print(*S)
print(cnt)
### BUGGY CODE ###

import math
def modpow(a,b,MOD):#a**b(MOD)
    if b == 0:
        return 1
    if b%2:
        return a*modpow(a**2%MOD,b//2,MOD)%MOD
    else:
        return modpow(a**2%MOD,b//2,MOD)
def modinv(a,MOD):
    return modpow(a,MOD-2,MOD)
MOD=998244353
n=int(input())
l=list(map(int,input().split()))
if l[0]!=0:
    print(0)
    exit()
else:
    l=l[1:]
if 0 in l:
    print(0)
    exit()
ans=1
tmp=1
for i in range(1,max(l)+1):
    c=l.count(i)
    ans*=modpow(tmp,c,MOD)
    ans%=MOD
    tmp=c
print(ans)

### FIXED CODE ###

import math
import collections
def modpow(a,b,MOD):#a**b(MOD)
    if b == 0:
        return 1
    if b%2:
        return a*modpow(a**2%MOD,b//2,MOD)%MOD
    else:
        return modpow(a**2%MOD,b//2,MOD)
MOD=998244353
n=int(input())
l=list(map(int,input().split()))
if l[0]!=0:
    print(0)
    exit()
else:
    l=l[1:]
if 0 in l:
    print(0)
    exit()
cl=collections.Counter(l)
ans=1
tmp=1
for i in range(1,max(l)+1):
    c=cl[i]
    if c==0:
        print(0)
        exit()
    ans*=modpow(tmp,c,MOD)
    ans%=MOD
    tmp=c
print(ans)
### BUGGY CODE ###

INF = 10 ** 12

N = int(input())
X = [0] * N
Y = [0] * N
P = [0] * N
for i in range(N):
    X[i], Y[i], P[i] = map(int,input().split())

score_X = []

for i in range(2 ** N):
    x = []
    I = i
    for j in range(N):
        i = I
        score = abs(X[j]) * P[j]
        for k in range(N):
            if i & 1:
                score = min(score, abs(X[j] - X[k]) * P[j])
            i >>= 1
        x.append(score)
    score_X.append(x)

score_Y = []

for i in range(2 ** N):
    y = []
    I = i
    for j in range(N):
        i = I
        score = abs(Y[j]) * P[j]
        for k in range(N):
            if i & 1:
                score = min(score, abs(Y[j] - Y[k]) * P[j])
            i >>= 1
        y.append(score)
    score_Y.append(y)

ans = [INF] * (N + 1)

for i in range(3 ** N):
    cnt = N
    index_X = 0
    index_Y = 0
    for j in range(N):
        index_X *= 2
        index_Y *= 2
        if i % 3 == 1:
            index_X += 1
        elif i % 3 == 2:
            index_Y += 1
        else:
            cnt -= 1
        i //= 3
    
    score = 0
    for j in range(N):
        score += min(score_X[index_X][j], score_Y[index_Y][j])
    
    ans[cnt] = min(ans[cnt], score)

for i in range(N + 1):
    print(ans[i])

### FIXED CODE ###

INF = 10 ** 12

N = int(input())
X = [0] * N
Y = [0] * N
P = [0] * N
for i in range(N):
    X[i], Y[i], P[i] = map(int,input().split())

score_X = []

for i in range(2 ** N):
    x = []
    I = i
    for j in range(N):
        i = I
        score = abs(X[j]) * P[j]
        for k in range(N):
            if i & 1:
                score = min(score, abs(X[j] - X[k]) * P[j])
            i >>= 1
        x.append(score)
    score_X.append(x)

score_Y = []

for i in range(2 ** N):
    y = []
    I = i
    for j in range(N):
        i = I
        score = abs(Y[j]) * P[j]
        for k in range(N):
            if i & 1:
                score = min(score, abs(Y[j] - Y[k]) * P[j])
            i >>= 1
        y.append(score)
    score_Y.append(y)

ans = [INF] * (N + 1)

for i in range(2 ** N):
    cnt = 0
    for j in range(N):
        if (i >> j) & 1:
            cnt += 1
    
    j = i
    
    while True:
        score = 0
        for k in range(N):
            if not (i >> k) & 1:
                score += min(score_X[j][k], score_Y[i - j][k])
        ans[cnt] = min(ans[cnt], score)
        if j == 0:
            break
        j = (j - 1) & i

for i in range(N + 1):
    print(ans[i])
### BUGGY CODE ###

import sys

sintinel = 1000000001

def merge_sort(A, l, r):
    if l + 1 < r:
        mid = (l + r) // 2
        merge_sort(A, l, mid)
        merge_sort(A, mid, r)
        merge(A, l, mid, r)

def merge(A, l, mid, r):
    global count
    for j in range(mid, r):
        y = j
        x = y - 1
        while l <= x and A[y] < A[x]:
            count += 1
            tmp = A[y]
            A[y] = A[x]
            A[x] = tmp
            y -= 1
            x -= 1

count = 0
n = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

merge_sort(A, 0, n)
print(count)

### FIXED CODE ###

import sys

sintinel = 1000000001

def merge_sort(A, l, r):
    if l + 1 < r:
        mid = (l + r) // 2
        cnt1 = merge_sort(A, l, mid)
        cnt2 = merge_sort(A, mid, r)
        cnt3 = merge(A, l, mid, r)
        return (cnt1 + cnt2 + cnt3)
    else:
        return 0

def merge(A, l, mid, r):
    n1 = len(A[l:mid])
    L = A[l:mid] + [sintinel]
    R = A[mid:r] + [sintinel]
    i = j = 0
    cnt = 0
    for k in range(l, r):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            cnt += n1 - i
            A[k] = R[j]
            j += 1
    return cnt

n = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

c = merge_sort(A, 0, n)
print(c)
### BUGGY CODE ###

N = int(input())
S = input()

after_cumsum_RGB = [[0]*(N+1), [0]*(N+1), [0]*(N+1)]

def rgb_hash(a):
  if S[i] == 'R':
    return 0
  elif S[i] == 'G':
    return 1
  elif S[i] == 'B':
    return 2
  
def ci_hash(a):
  if 'R' not in a:
    return 0
  elif 'G' not in a:
    return 1
  elif 'B' not in a:
    return 2

def c_hash(a):
  if 'R' not in a:
    return 'R'
  elif 'G' not in a:
    return 'G'
  elif 'B' not in a:
    return 'B'
  
for i in range(N-1, -1, -1):
  if S[i] == 'R':
    after_cumsum_RGB[0][i] = 1
  if S[i] == 'G':
    after_cumsum_RGB[1][i] = 1
  if S[i] == 'B':
    after_cumsum_RGB[2][i] = 1
  for j in range(3):
    after_cumsum_RGB[j][i] += after_cumsum_RGB[j][i+1]

ans = 0
for i in range(0, N-2):
  for j in range(i+1, N-1):
    if S[i] != S[j]:
      target = ci_hash([S[i], S[j]])
      ans += after_cumsum_RGB[target][j+1]
      if 2*j-i <= N-1:
        if S[2*j-i] == c_hash([S[i], S[j]]):
          ans -= 1
print(ans)
      
    

### FIXED CODE ###

N = int(input())
S = input()

R = S.count('R')
G = S.count('G')
B = N - R - G

ans = R * G * B

for i in range(0, N-2):
  for j in range(i+1,N-1):
    k = 2 * j - i
    if k >= N:
      break
    else:
      if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
        ans -= 1

print(ans)