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

if __name__ == '__main__':
    length, question_count = map(int, input().split())

    string = input()
    for i in range(question_count):
        l, r = map(int, input().split())
        current_string = string[l - 1:r]
        print(current_string.count('AC'))


### FIXED CODE ###

if __name__ == '__main__':
    length, question_count = map(int, input().split())

    string = input()
    ac_sums = [0]
    for i in range(1, len(string) + 1):
        if i > 1 and string[i - 2] == 'A' and string[i - 1] == 'C':
            ac_sums.append(ac_sums[i - 1] + 1)
        else:
            ac_sums.append(ac_sums[i - 1])

    for i in range(question_count):
        l, r = map(int, input().split())
        ans = ac_sums[r] - ac_sums[l - 1]
        if l > 1 and string[l - 1] == 'C' and string[l - 2] == 'A':
            ans -= 1
        print(ans)
### BUGGY CODE ###

K,S = map(int,input().split())
ans = 0

for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x+y+z==S:
                ans+=1
print(ans)

### FIXED CODE ###

K,S = map(int,input().split())
ans = 0

for x in range(K+1):
    for y in range(K+1):
        z = S-(x+y)
        if 0 <= z <= K:
            ans+=1
print(ans)
### BUGGY CODE ###

n=int(input())
a=[int(input()) for _ in range(n)]
b=[1]
buf=1
if 2 not in a:
    print(-1)
else:
    while True:
        a_buf=a[buf-1]
        if a_buf==2:
            print(len(b))
            break
        elif a_buf in b:
            print(-1)
            break
        b.append(a_buf)
        buf=a_buf

### FIXED CODE ###

n=int(input())
a=[int(input()) for _ in range(n)]
b=[1]
buf=1
count=0
if 2 not in a:
    print(-1)
else:
    while count<n:
        a_buf=a[buf-1]
        #print("buf,a[buf-1],b=",buf,a[buf-1],b)
        if a_buf==2:
            #print("check_2")
            print(len(b))
            break
        #elif a_buf in b:
            #print("check_loop")
            #print(-1)
            #break
        b.append(a_buf)
        buf=a_buf
        count+=1
    if count==n:
        print(-1)
### BUGGY CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
from functools import lru_cache
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))
def inp_str():
    '''
    一行の文字をlistで取得
    '''
    return list(input())[:-1]
def inpl_str():
    '''
    一行に複数の文字
    '''
    return list(input().split())

class Angle():
    DIAGONAL = 0
    UP = 1
    LEFT = 2

s = inp_str()
t = inp_str()
n = len(s)
m = len(t)
class node():
    def __init__(self):
        self.value = 0
        self.angle = None
        self.ans=""
dp = [[node() for j in range(m+1)] for i in range(n+1)]
for i in range(1,n + 1):
    dp[i][0].angle = Angle.UP
for j in range(1,m + 1):
    dp[0][j].angle = Angle.LEFT
for i in range(n):
    for j in range(m):
        same = dp[i][j].value + 1 if s[i] == t[j] else -1
        up = dp[i][j+1].value
        left = dp[i+1][j].value
        option = [same, up, left]
        max_index = option.index(max(option))
        dp[i + 1][j + 1].value = max(option)
        dp[i + 1][j + 1].angle = max_index
        if max_index == Angle.DIAGONAL:
            dp[i + 1][j + 1].ans = dp[i][j].ans + s[i]
        elif max_index == Angle.LEFT:
            dp[i + 1][j + 1].ans = dp[i + 1][j].ans
        else:
            dp[i + 1][j + 1].ans = dp[i][j+1].ans

            
# print(dp[n][m].value)
# for i in range(n+1):
#     for j in range(m+1):
#         print(dp[i][j].value,end="")
#     print("")
# print("")
# print("")
# for i in range(n+1):
#     for j in range(m+1):
#         print(dp[i][j].ans,end="")
#     print("")
print(dp[n][m].ans)

        

### FIXED CODE ###

import sys
input = sys.stdin.readline

s = list(input())
t = list(input())
n = len(s)-1
m = len(t)-1
value = [[0]*(m+1) for i in range(n+1)]


for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            value[i + 1][j + 1] = value[i][j] + 1
        elif value[i][j + 1] > value[i + 1][j]: #UP
            value[i + 1][j + 1] = value[i][j + 1]
        else:  # LEFT
            value[i + 1][j + 1] = value[i + 1][j]
i = n-1
j = m-1
ans=""
while i >= 0 and j >= 0:
    if s[i] == t[j]:
        ans = s[i] + ans
        i -= 1
        j -= 1
    elif value[i][j + 1] > value[i + 1][j]:
        i -= 1
    else:
        j -= 1
print(ans)
### BUGGY CODE ###

n = int(input())
a = [int(x) for x in input().split()]

def is_satisfied(s):
    ln = len(s)
    check = [s.count(i) == 2 for i in range(ln - 1, 1, -2)]
    if ln % 2 == 0:
        check.append(s.count(1) == 2)
    else:
        check.append(s.count(0) == 1)

    return all(check)


ans = 2 ** (n // 2) % (10 ** 9 + 7)
print(ans if is_satisfied(a) else 0)


### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split()]

def is_satisfied(s):
    ln = len(s)
    check = sorted(list(range(ln - 1, 1, -2)) * 2)
    if ln % 2 == 0:
        check.insert(0, 1)
        check.insert(0, 1)
    else:
        check.insert(0, 0)

    return sorted(s) == check

    # for i in range(ln - 1, 1, -2):
    #     if not s.count(i) == 2:
    #         return False
    # if ln % 2 == 0:
    #     if not s.count(1) == 2:
    #         return False
    # else:
    #     if not s.count(0) == 1:
    #         return False

    # return True


ans = 2 ** (n // 2) % (10 ** 9 + 7)
print(ans if is_satisfied(a) else 0)
### BUGGY CODE ###

n = int(input())

x = (10**9 + 7)
k=1
for i in range(1,n+1):
  k = k * i

  
  
if k <x:
  print(k)
else:
  print(k % x)


### FIXED CODE ###

n = int(input())

x = (10**9 + 7)
k=1
for i in range(1,n+1):
  k = k * i
  k = k%x

print(k)
### BUGGY CODE ###

n=int(input())
m=[]
o=[1]
ans=0
for i in range(n):
    s=input()
    l=[0]*26
    for v in range(10):
        if s[v]=="a":
            l[0]+=1
        elif s[v]=="b":
            l[1]+=1
        elif s[v]=="c":
            l[2]+=1
        elif s[v]=="d":
            l[3]+=1
        elif s[v]=="e":
            l[4]+=1
        elif s[v]=="f":
            l[5]+=1
        elif s[v]=="g":
            l[6]+=1
        elif s[v]=="h":
            l[7]+=1
        elif s[v]=="i":
            l[8]+=1
        elif s[v]=="j":
            l[9]+=1
        elif s[v]=="k":
            l[10]+=1
        elif s[v]=="l":
            l[11]+=1
        elif s[v]=="n":
            l[12]+=1
        elif s[v]=="m":
            l[13]+=1
        elif s[v]=="o":
            l[14]+=1
        elif s[v]=="p":
            l[15]+=1
        elif s[v]=="q":
            l[16]+=1
        elif s[v]=="r":
            l[17]+=1
        elif s[v]=="s":
            l[18]+=1
        elif s[v]=="t":
            l[19]+=1
        elif s[v]=="u":
            l[20]+=1
        elif s[v]=="v":
            l[21]+=1
        elif s[v]=="w":
            l[22]+=1
        elif s[v]=="x":
            l[23]+=1
        elif s[v]=="y":
            l[24]+=1
        else:
            l[25]+=1
    m.append(l)
m.sort()
for k in range(1,n):
    if m[k]==m[k-1]:
        o[-1]+=1
    else:
        o.append(1)
for _ in range(len(o)):
    if o[_]==1:
        pass
    else:
        c=(o[_]*(o[_]-1))//2
        ans+=c
print(ans)

### FIXED CODE ###

n=int(input())
d={}
ans=0
for i in range(n):
    s=sorted(list(input()))
    e=""
    for v in range(10):
        e+=s[v]
    if e in d:
        d[e]+=1
    else:
        d[e]=1
for _ in d:
    if d[_]==1:
        pass
    else:
        ans+=d[_]*(d[_]-1)//2
print(ans)
### BUGGY CODE ###

import numpy as np

h,w = map(int,input().split(" "))
s = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    tmp = list(input())
    for j in range(w):
        s[i][j] = tmp[j]

dp1 = np.full((2000,2000),-1)
dp2 = np.full((2000,2000),-1)
dp3 = np.full((2000,2000),-1)
dp4 = np.full((2000,2000),-1)



for i in range(h):
    for j in range(w-1,-1,-1):
        if s[i][j] == "#":
            dp2[i][j] = 0
        elif j == w-1:
            dp2[i][j] = 1
        else:
            dp2[i][j] = 1 + dp2[i][j+1]

for i in range(w):
    for j in range(h):
        if s[j][i] == "#":
            dp3[j][i] = 0
        elif j == 0:
            dp3[j][i] = 1
        else:
            dp3[j][i] = 1 + dp3[j-1][i]

        if s[h-j-1][i] == "#":
            dp4[h-j-1][i] = 0
        elif h-j-1 == h-1:
            dp4[h-j-1][i] = 1
        else:
            dp4[h-j-1][i] = 1 + dp4[h-j][i]


a = 1
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            dp1[i][j] = 0
        elif j == 0:
            dp1[i][j] = 1
        else:
            dp1[i][j] = 1 + dp1[i][j-1]
        a = max(a,dp1[i][j]+dp2[i][j]+dp3[i][j]+dp4[i][j]-3)

print(int(a))

### FIXED CODE ###

h,w = map(int,input().split(" "))
s = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    tmp = list(input())
    for j in range(w):
        s[i][j] = tmp[j]

dp1= []
dp2= [[-1 for i in range(w)] for j in range(h)]
dp3=[]
dp4=[[-1 for i in range(w)] for j in range(h)]


for i in range(h):
    dp1.append([])
    dp3.append([])
    for j in range(w):
        dp1[i].append(-1)
        dp3[i].append(-1)

        if s[i][j] == "#":
            dp1[i][j] = 0
        elif j == 0:
            dp1[i][j] = 1
        else:
            dp1[i][j] = 1 + dp1[i][j-1]

        if s[i][w-j-1] == "#":
            dp2[i][w-j-1] = 0
        elif w-j-1 == w-1:
            dp2[i][w-j-1] = 1
        else:
            dp2[i][w-j-1] = 1 + dp2[i][w-j]

        if s[i][j] == "#":
            dp3[i][j] = 0
        elif i == 0:
            dp3[i][j] = 1
        else:
            dp3[i][j] = 1 + dp3[i-1][j]

        if s[h-i-1][j] == "#":
            dp4[h-i-1][j] = 0
        elif h-i-1 == h-1:
            dp4[h-i-1][j] = 1
        else:
            dp4[h-i-1][j] = 1 + dp4[h-i][j]



        

a = 1
for i in range(h):
    for j in range(w):
        a = max(a,dp1[i][j]+dp2[i][j]+dp3[i][j]+dp4[i][j]-3)


print(a)
### BUGGY CODE ###

import math

Q = int(input())

def prime(n):
	if n > 1:
		for i in range(2,math.floor(math.sqrt(n))+1):
			if (n % i) == 0:
				return(False)
				break
		else:
			return(True)
	else:
		return(False)

Numero = [0]*100001
for i in range (1, 50001):
	if prime(2*i+1) == 1 and prime(i+1) == 1:
		for j in range (2*i+1, 100001):
			Numero[j]+=1
	else:
		continue

for i in range (0, Q):
	A, B = map(int, input().split())
	print(Numero[B+1]-Numero[A])

### FIXED CODE ###

import math

Q = int(input())

def prime(n):
	if n > 1:
		for i in range(2,math.floor(math.sqrt(n))+1):
			if (n % i) == 0:
				return(False)
				break
		else:
			return(True)
	else:
		return(False)

Numero = [0]*100001
for i in range (1, 50001):
	if prime(2*i+1) == 1 and prime(i+1) == 1:
		for j in range (2*i+1, 100001):
			Numero[j]+=1
	else:
		continue

for i in range (0, Q):
	A, B = map(int, input().split())
	print(Numero[B]-Numero[A-1])
### BUGGY CODE ###

def solve():
    N, C = map(int, raw_input().split())
    xs, vs = [], []
    for i in range(N):
        x, v = map(int, raw_input().split())
        xs.append(x)
        vs.append(v)
    xs, vs = map(list, zip(*sorted(zip(xs, vs), key=lambda _: _[0])))
    a = f(xs, vs, N, C)
    b = f(map(lambda x: C-x, xs[::-1]), vs[::-1], N, C)
    ans = max(a, b)
    return ans

def f(xs, vs, N, C):
    best = 0
    cur = 0
    px = 0
    best_index = -1
    targets = [(best_index, best)]
    for i in range(N):
        x, v = xs[i], vs[i]
        cur += v - abs(x-px)
        if best < cur:
            best_index = i
            best = cur
            targets.append((best_index, best))
        px = x
    for target_index, target in targets:
        cur = target
        if target_index != -1:
            cur -= xs[target_index]
        px = C
        for i in range(N-1, target_index, -1):
            x, v = xs[i], vs[i]
            cur += v - abs(x-px)
            if best < cur:
                best = cur
            px = x
    return best

print solve()

### FIXED CODE ###

def solve():
    N, C = map(int, raw_input().split())
    xs, vs = [], []
    for i in range(N):
        x, v = map(int, raw_input().split())
        xs.append(x)
        vs.append(v)
    xs, vs = map(list, zip(*sorted(zip(xs, vs), key=lambda _: _[0])))
    a = f(xs, vs, N, C)
    b = f(map(lambda x: C-x, xs[::-1]), vs[::-1], N, C)
    ans = max(a, b)
    return ans

def f(xs, vs, N, C):
    ws = []
    best = 0
    cur = 0
    px = C
    for i in range(N-1,-1,-1):
        x, v = xs[i], vs[i]
        cur += v - abs(x-px)
        best = max(best, cur)
        px = x
        ws.append(best)
    ws = ws[::-1]
    best = 0
    cur = 0
    px = 0
    for i in range(N):
        x, v = xs[i], vs[i]
        cur += v - abs(x-px)
        best = max(best, cur)
        if i+1 < N:
            best = max(best, cur+ws[i+1]-x)
        px = x
    return best

print solve()
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
for i in range(1, n+1):
    print(a.count(i))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
x = [0]*n
for i in a:
    x[i-1] += 1
for j in x:
    print(j)
### BUGGY CODE ###

MOD = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))
s = 0
m = 1
for i in range(60):
    c = 0
    for j in range(n):
        c += (a[j] & m)//m
    s = (s + m*c*(n-c))%MOD
    m <<= 1
print(s)

### FIXED CODE ###

MOD = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))
s = 0
m = 1
for i in range(60):
    c = sum(ai & m for ai in a)
    c //= m
    s = (s + m*c*(n-c))%MOD
    m <<= 1
print(s)
### BUGGY CODE ###

n = int(input())
A = [int(i) for i in input().split()]

s = [0]*61
for a in A:
    cnt = 0
    while a != 0:
        # print(cnt,a)
        if(a&1)==1:
            s[cnt+1] += 1
        cnt+=1
        a = a >> 1
ans = 0
for i in range(61):
    # print("a",2**(i-1)*s.get(i,0)*(n-s.get(i,0)))
    # print("b",s.get(i,0))
    # print("c",(n-s.get(i,0)))
    ans += (2**(i-1)*s[i]*(n-s[i])) % (10**9+7)
ans = ans % (10**9+7)
print(int(ans))
# print(s)


### FIXED CODE ###

n = int(input())
A = [int(i) for i in input().split()]

s = [0]*61
for a in range(n):
    for i in range(61):
        if(A[a]>>i&1)==1:
            s[i+1] += 1
ans = 0
for i in range(60):
    # print("a",2**(i-1)*s.get(i,0)*(n-s.get(i,0)))
    # print("b",s.get(i,0))
    # print("c",(n-s.get(i,0)))
    ans += 2**(i)*s[i+1]*(n-s[i+1])
ans = ans % (10**9+7)
print(int(ans))
# print(s)
### BUGGY CODE ###

n,k = map(int, input().split( ))
h = list(map(int, input().split( )))
#h = [0]+h#h[0]=0追加
inf = 10**15

dp = [[inf]*n for _ in range(n+1)] #dp[i][j]右端がi、j+1本残す
mn = h[0]
for i in range(n):
    mn = min(mn,h[i])
    dp[i][0] = min(mn,h[i])

for i in range(n):##右端
    for j in range(i+1):#本数+1
        for t in range(i):#右から2番目,+1
            dp[i][j] = min(dp[i][j], dp[t][j-1] + max(h[i]-h[t], 0))

ans = inf 

for i in range(n):
    ans = min(ans, min(dp[i][n-k-1:]))
print(ans)


### FIXED CODE ###

n,k = map(int, input().split( ))
if n==k:
    print(0)
    exit()
h = list(map(int, input().split( )))
#h = [0]+h#h[0]=0追加
inf = 10**15

dp = [[inf]*n for _ in range(n+1)] #dp[i][j]右端がi、j+1本残す
mn = h[0]
for i in range(n):
    #mn = min(mn,h[i])
    dp[i][0] = h[i]#min(mn,h[i])

for i in range(1,n):##右端
    for j in range(i+1):#本数
        for t in range(j-1,i):#右から2番目,
            dp[i][j] = min(dp[i][j], dp[t][j-1] + max(h[i]-h[t], 0))

ans = inf 

for i in range(n):
    ans = min(ans, min(dp[i][n-k-1:]))###
print(ans)
### BUGGY CODE ###

import numpy as np
N, M = map(int, input().split())
A = np.array([int(_) for _ in input().split()])
B = [0] * M
C = [0] * M
A.sort()
for m in range(M):
    b, c = map(int, input().split())
    A[:b] = np.where(A[:b] < c, c, A[:b])

    A.sort()
    #print(A)
print(sum(A))

### FIXED CODE ###

import sys
N, M = map(int, input().split())
A = [int(_) for _ in input().split()]
A.sort()
#print(A)
BC = [0] * M
for m in range(M):
    BC[m] = list(map(int, input().split()))
BC.sort(key=lambda x: x[1], reverse=True)
#print(BC)
c = 0
for m in range(M):
    for t in range(BC[m][0]):
        if BC[m][1] > A[c]:
            A[c] = BC[m][1]
        c += 1
        if c == N:
            print(sum(A))
            sys.exit()
print(sum(A))
### BUGGY CODE ###

n=int(input())
x=list(map(int,input().split()))
m=len(x)//2-1
for i in range(len(x)):
    t = sorted(x[0:i] + x[i+1:])
    print(t[m])

### FIXED CODE ###

def main():
    n=int(input())
    x=list(map(int,input().split()))
    sx = sorted(x)
    lx = len(x)//2
    m = sx[lx]
    _m = sx[lx-1] if 0 < m-1 else sx[0]
    for i in x:
        print(m if i<m else _m)

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


string = input()
N=int(input())
Que = []
for i in range(N):
	Que.append(input())

for Q in Que:	
	if Q[0] == '1':
		string = string[::-1]
	else:
		T,F,C = Q.split(' ')
		if F == '1':
			string = C + string
		elif F == '2':
			string += C
print(string)

### FIXED CODE ###

string = input()
N=int(input())
Que = []
for i in range(N):
	Que.append(input())

init = ""
end = ""
rev = 2
for Q in Que:	
	if int(Q[0]) == 1:
		if rev != 1:
			rev=1
		else:
			rev=2
	elif int(Q[0])==2:
		T,F,C = Q.split(' ')
		if rev == 1:
			if int(F) == 1:
				F =2
			else:
				F = 1
		if int(F) == 1:
			init = init+C
		elif int(F) == 2:
			end = end + C
final = init[-1::-1]+string+end
if rev == 1:
	print(final[-1::-1])
else:
	print(init[-1::-1]+string+end)
### BUGGY CODE ###

import sys
from collections import Counter

n=int(input())
a=[0]+[list(map(int,sys.stdin.readline().strip().split()[::-1])) for _ in range(n)]

pairs=n*(n-1)//2
ans=0

while pairs>0:
    ans+=1
    tpairs=0
    x=[]

    for i in range(1,n+1):
        if len(a[i])==0:
            continue
        lasta=a[i][-1]
        x.append((min(i,lasta),max(i,lasta)))
    
    cnt=Counter(x)

    for (i,j),v in cnt.most_common():
        if v==1:
            break

        a[i].pop()
        a[j].pop()
        tpairs+=1
    
    if tpairs==0:
        print(-1)
        break

    pairs-=tpairs
else:
    print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

n=int(input())
g=[set() for _ in range(n*(n-1)//2+1)]
visit=[0]*(n*(n-1)//2+1)
d=[0]*(n*(n-1)//2+1)

for i in range(1,n+1):
    last=0
    for j in list(map(int,input().split())):
        mi,ma=(min(i-1,j-1),max(i-1,j-1))
        current=ma*(ma-1)//2+mi+1
        g[last].add(current)
        last=current

def dfs(u):
    if visit[u]==2:
        return d[u]
    
    ans=0
    visit[u]=1
    for v in g[u]:
        if visit[v]==1:
            print(-1)
            exit(0)
        
        d[u]=max(d[u],1+dfs(v))
    
    visit[u]=2
    return d[u]

print(dfs(0))
### BUGGY CODE ###

n = int(input())
s = list(input())
cmin = []

for i in range(n):
	west = s[:i-1]
	east = s[i+1:]
	change = west.count("W") + east.count("E")
	cmin.append(change)

print(min(cmin))

### FIXED CODE ###

import numpy as np
N = int(input())
S = list(input())

Wleft = np.zeros(N, dtype = int)
Eright = np.zeros(N, dtype = int)
Eright[0] = (S.count("E") if S[0] == "W" else S.count("E") - 1)
for i in range(N-1):
    if S[i] == "W":
        Wleft[i+1] = Wleft[i]+1
    else:
        Wleft[i+1] = Wleft[i]
    if S[i+1] == "E":
        Eright[i+1] = Eright[i] - 1
    else:
        Eright[i+1] = Eright[i]
total = Wleft + Eright
print(np.min(total))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
mA = max(A)
max_long = min(N,max(A)*2)
count = 0
for i in range(N-1):
  m = min(N,i+max_long+1)
  for j in range(i+1,m):
    if j-i == A[i]+A[j]:
      count += 1
print(count)

### FIXED CODE ###

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

ans = 0
B = [0]*N
C = [0]*N

for i in range(N):
  b = i+A[i]
  c = i-A[i]
  if 0 < b < N:
    B[b] += 1
  if 0 < c < N:
    C[c] += 1

for i in range(N):
  ans += B[i]*C[i]

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

n = int(input())

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

a = 1
qs = [ps[0]]
for i in range(1,n):
    if min(qs) >= ps[i]:
        a += 1
    qs.append(ps[i])

print(a)


### FIXED CODE ###

n = int(input())

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

a = 0
m = n + 1
qs = []
for i in range(n):
    if m >= ps[i]:
        a += 1
    qs.append(ps[i])
    m = min(m,ps[i])
    if ps[i] == 1:
        break

print(a)
### BUGGY CODE ###

N=int(input())
S=input()
ans=0
for i in range(N):
    for j in range(i+1,N):
        if S[i]!=S[j]:
            for k in range(j+1,N):
                if (j-i)!=(k-j):
                    if S[j]!=S[k] and S[i]!=S[k]:
                        ans+=1
print(ans)


### FIXED CODE ###

N=int(input())
S=input()
r,g,b=0,0,0
for i in range(N):
    if S[i]=="R":
        r+=1
    elif S[i]=="G":
        g+=1
    elif S[i]=="B":
        b+=1
# j-i=k-j  2j-i-k=0 k=i-2j について調べるもしRGBなら、それをrgbからマイナスする
tmp=0
for i in range(N):
    for j in range(i+1,N):
        k=2*j-i
        if k<N and k>=0:
            if S[i]!=S[j] and S[i]!=S[k] and S[j]!=S[k]:
                tmp+=1
# print("rgb",r*g*b)
# print("tmp",tmp)
print(r*g*b-tmp)
### BUGGY CODE ###

n = int(input())
p = list(map(int, input().split()))
p_min = p[0]
p_sum = 1

for i in range(n):
    # リストを前から順にスライス
    p_new = p[0:i+1]
    
    # スライスしたリストの中の最小値を取得
    p_new_min = min(p_new)

    # 今までの最小値と比較して小さい場合
    if p_new_min < p_min:
        p_sum += 1
        # 最小値の更新
        p_min = p_new_min

print(p_sum)

### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))
p_min = p[0]
p_sum = 1

# リストの前から最小値を検索
for i in range(1, n):
    
    # 最小値を見つけた場合
    if p_min > p[i]:
        p_sum += 1
        # 最小値を更新
        p_min = p[i]

print(p_sum)
### BUGGY CODE ###

n,k = map(int,input().split())
a = [int(n) for n in input().split()]

cur = 1
for i in range(k):
    cur *= a[i]

for i in range(k,n):
    nxt = cur // a[i - k] * a[i]
    if (nxt > cur):
        print("Yes")
    else:
        print("No")
    cur = nxt


### FIXED CODE ###

n,k = map(int,input().split())
a = [int(n) for n in input().split()]

for i in range(k,n):
    if (a[i] > a[i - k]):
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

N,M = map(int, input().split())
answer_p = set()
submit_p= set()
L=[]
count_pena=0

for _ in range(M):
  p,S= input().split()
  answer_p.add(p)
  if (p, 'AC') in L:
    continue
  L.append((p,S))

for l in L:
  if l[0] not in answer_p:
    continue
  else:
    if l[1]=='WA':
      count_pena+=1

print(len(answer_p), count_pena)

### FIXED CODE ###

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

N,M = map(int, readline().split())
PS = [line.split() for line in readlines()]

AC = [False] * (N+1)
WA_cnt = [0] * (N+1)

penal = 0
for p,s in PS:
  p = int(p)
  if AC[p]:
    continue
  if s== b'WA':
    WA_cnt[p] += 1
  else:
    AC[p] = True
    penal += WA_cnt[p]
    
ac = sum(AC)
print(ac, penal)
### BUGGY CODE ###

N,K = map(int, input().split())
h = list(map(int, input().split()))
dp = [float('inf')]*len(h)
dp[0] = 0
for i in range(N):
    if i<N-K:
        for k in range(1,K+1):
            dp[i+k] = min(dp[i]+abs(h[i]-h[i+k]), dp[i+k])
    else:
        for k in range(1, N-i):
            dp[i+k] = min(dp[i]+abs(h[i]-h[i+k]), dp[i+k])
print(dp[-1])

### FIXED CODE ###

N,K = map(int, input().split())
h = list(map(int, input().split()))
dp = [float('inf')]*len(h)
dp[0] = 0
for i in range(N):
    if i<N-K:
        for k in range(1,K+1):
            dp[i+k] = min(dp[i]+abs(h[i]-h[i+k]), dp[i+k])
    else:
        for k in range(1, N-i):
            dp[i+k] = min(dp[i]+abs(h[i]-h[i+k]), dp[i+k])
print(dp[-1])
### BUGGY CODE ###

li = list(map(int,input().split()))
K, S = li[0], li[1]

count = 0

for x in range(K + 1):
  for y in range(K + 1):
    for z in range(K + 1):
      if x + y + z == S:
        count += 1

print(count)

### FIXED CODE ###

li = list(map(int,input().split()))
K, S = li[0], li[1]

count = 0

for x in range(K + 1):
  for y in range(K + 1):
      z = S - x - y
      if z >= 0 and z <= K:
        count += 1

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

N=int(input())

print(sum(range(1,N)))

### FIXED CODE ###

N=int(input())

print(sum(range(1,N)))