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

n,q = map(int,input().split())
s = input()
word = list(s)
li = [list(input().split()) for _ in range(q)]


def dfs(m):
    for i in range(q):
        if word[m] == li[i][0]:
            if li[i][1] == 'R':
                m += 1
            else:
                m -= 1
        if m < 0:
            return 'Left'
        elif m > n-1:
            return  'Right'
    return True

def left(a,b):
    if a == 0 and b == n-1:
        if dfs(a) != 'Left':
            return 0
        elif dfs(b) == 'Left':
            return n
    m = int((a+b)/2)
    if a == m:
        return b
    if dfs(m) == 'Left':
        return left(m,b)
    else:
        return left(a,m)

def right(a,b):
    if a == 0 and b == n-1:
        if dfs(b) != 'Right':
            return n-1
        elif dfs(a) == 'Right':
            return -1
    m = int((a+b)/2)
    if a == m:
        return a
    if dfs(m) == 'Right':
        return right(a,m)
    else:
        return right(m,b)

print(right(0,n-1) - left(0,n-1) + 1)


### FIXED CODE ###

n,q = map(int,input().split())
s = input()
word = list(s)
li = [list(input().split()) for _ in range(q)]
memo = {}

def dfs(m):
    k = m
    if m in memo:
        return memo[m]
    for x in li:
        if word[m] == x[0]:
            if x[1] == 'R':
                m += 1
            else:
                m -= 1
        if m < 0:
            memo[k] = 'Left'
            return 'Left'
        elif m > n-1:
            memo[k] = 'Right'
            return  'Right'
    memo[k] = True
    return True

def left(a,b):
    m = int((a+b)/2)
    if a == m:
        return b
    elif dfs(m) == 'Left':
        return left(m,b)
    else:
        return left(a,m)

def right(a,b):
    m = int((a+b)/2)
    if a == m:
        return a
    elif dfs(m) == 'Right':
        return right(a,m)
    else:
        return right(m,b)

if dfs(0) == 'Right':
    print(0)
elif dfs(0) == 'Left':
    if dfs(n-1) == 'Right':
        print(right(0,n-1) - left(0,n-1) + 1)
    elif dfs(n-1) == 'Left':
        print(0)
    else:
        print(n - left(0,n-1))
else:
    if dfs(b) == 'Right':
        print(right(0,n-1) + 1)
    elif dfs(b) == 'Left':
        print(0)
    else:
        print(n)
### BUGGY CODE ###

from collections import defaultdict
class UnionFind:


    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.rank = [0]*n
        self.n = n
    def find(self,x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same(self,x,y):
        return bool(self.find(x)==self.find(y))
    def sameset(self):
        ret = defaultdict(set)
        for i in range(self.n):
            ret[self.find(i)] = ret[self.find(i)] | {i}
        return ret

from sys import stdin
def main():
    N,K,L = map(int,stdin.readline().split())
    uf = UnionFind(N)
    uf1 = UnionFind(N)
    ans = [0 for _ in range(N)]
    for _ in range(K):
        p,q = map(int,stdin.readline().split())
        uf.union(p-1,q-1)
    for _ in range(L):
        r,s = map(int,stdin.readline().split())
        uf1.union(r-1,s-1)
    a = uf.sameset()
    b = uf1.sameset()
    for u in a.values():
        for v in b.values():
            tmp = list(u&v)
            if tmp:
                l = len(tmp)
                for j in tmp:
                    ans[j] += l
            else:continue
    print(*ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import defaultdict
class UnionFind:


    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.rank = [0]*n
        self.n = n
    def find(self,x):
        if self.parent[x] == x:
            return x
        while x != self.parent[x]:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same(self,x,y):
        return bool(self.find(x)==self.find(y))

from sys import stdin
def main():
    N,K,L = map(int,stdin.readline().split())
    uf = UnionFind(N)
    uf1 = UnionFind(N)

    for _ in range(K):
        p,q = map(int,stdin.readline().split())
        uf.union(p-1,q-1)
    for _ in range(L):
        r,s = map(int,stdin.readline().split())
        uf1.union(r-1,s-1)
    d = defaultdict(int)
    for i in range(N):
        d[(uf.find(i),uf1.find(i))] += 1
    print(*(d[uf.find(i),uf1.find(i)]for i in range(N)))
    #print(l)

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

def main():
  import fractions
  import math

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

  if a>b:
    a,b = b,a
  
  d = [1]
  num = 2

  while num <= min(a,b):
    if a%num == 0 and b%num == 0:
      d.append(num)
      while a%num == 0 and a>0:
        a = a//num
      while b%num == 0 and b>0:
        b = b//num
    num+=1
  
  print(len(d))

if __name__ == "__main__":
  main()


### FIXED CODE ###

def main():
  import fractions
  import math

  a,b = map(int,input().split())
  g = fractions.gcd(a,b)
  
  d = [1]
  num = 2

  while num**2 <= g:
    #print("num",num)
    if g%num == 0:
      d.append(num)
    while g%num == 0 and g>1:
      g = g//num
      #print(g)
    num += 1
  
  print(len(d) + (g > 1))

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

import numpy as np
import math
input1 = list(map(int,input().split()))

X = input1[0]
Y = input1[1]

if (X+Y) % 3 != 0:
  print(0)
  exit()

if Y<X/2:
  print(0)
  exit()

if Y>X*2:
  print(0)
  exit()

s = int((2*X-Y)/3)
t = int((-X+2*Y)/3)

n = s+t
r = min(s,t)

def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p


ans = comb(n,r,10**9+7)
print(ans)

### FIXED CODE ###

import numpy as np
import math
input1 = list(map(int,input().split()))

X = input1[0]
Y = input1[1]

if (X+Y) % 3 != 0:
  print(0)
  exit()

if Y<X/2:
  print(0)
  exit()

if Y>X*2:
  print(0)
  exit()

s = int((2*X-Y)/3)
t = int((-X+2*Y)/3)

n = s+t
r = min(s,t)

def comb(n,k,p):
  if n==0 or k==0: return 1

  a=1
  for i in range(1,n+1):
    a*=i
    if a >= p:
      a = a%p

  b=1
  for i in range(1,k+1):
    b*=i
    if b >= p:
      b = b%p

  c=1
  for i in range(1,n-k+1):
    c*=i
    if c >= p:
      c = c%p

  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p


ans = comb(n,r,10**9+7)
print(ans)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import collections
import sys
 
input=sys.stdin.readline
 
N=int(input())
l=[]
clist=[]
 
for i in range(N):
    l.append(list(input().replace("\n","")))
    clist.append(collections.Counter(l[-1]))
    #clist.append(collections.Counter(list(input().replace("\n",""))))#ここは普通に入れてfor文でcounterする
 
count=0
 
for i in range(N):
    for j in range(i+1,N):
        if clist[i]==clist[j]:
            count+=1
            
print(count)

### FIXED CODE ###

# coding: utf-8
# Your code here!
import collections 
 
N=int(input())
l=[]
 
for i in range(N):
    l.append(list(input()))
    l[i].sort()
    l[i]="".join(l[i])
    
clist=list(collections.Counter(l).values())

count=0
for c in clist:
    count+=int(c*(c-1)//2)
    
print(count)
### BUGGY CODE ###

N = int(input())
p = []

for i in range(N):
    a = int(input())
    if not a in p:
        p.append(a)
    else:
        p.remove(a)

print(len(p))


### FIXED CODE ###

N = int(input())
p = []

for i in range(N):
    p.append(input())

p.sort()
c = 1
ans = 0
for i in range(1, len(p)):
    if p[i] == p[i - 1]:
        c += 1
    else:
        if c % 2 == 1:
            ans += 1
        c = 1
if c % 2 == 1:
    ans += 1
print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split())
glp = [[] for i in range(N+1)]
counter = [0]*N

for _ in range(N-1):
    a, b = map(int, input().split())
    glp[a].append(b)

for i, g in enumerate(glp):
    for gi in g:
        glp[i].extend(glp[gi])

for i in range(Q):
    p, x = map(int, input().split())
    for pi in glp[p]:
        counter[pi-1] += x
    counter[p-1] += x
    
print(" ".join(map(str,counter)))

### FIXED CODE ###

N,Q = map(int, input().split())
parentNodes = [0] * (N+1) #i番目のノードの親番号
counter = [0] * (N+1)

for i in range(N-1):
	a, b = map(int, input().split())
	parentNodes[b] = a
 
for _ in range(Q):
	p,x = map(int, input().split())
	counter[p] += x
 
for i in range(1,N+1):
	counter[i] += counter[parentNodes[i]]
 
print(*counter[1:])
### BUGGY CODE ###

import math
import queue
from collections import defaultdict
 
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def printQueue(q):
	r=q
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)

s = readChar()
q = readInt()
qa = []
for i in range(q):
	x = input()
	if x=="1":
		qa.append([1,0,0])
	else:
		x = x.split()
		qa.append([int(x[0]),int(x[1]),x[2]])

def t1(s):
	return s[::-1]

def t2(f,c,s):
	if f==1:
		return c+s
	else:
		return s+c

for a in qa:
	if a[0]==1:
		s=t1(s)
	else:
		s=t2(a[1],a[2],s)

print(s)

### FIXED CODE ###

import math
import queue
from collections import defaultdict
 
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def printQueue(q):
	r=q
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)

s = readChar()
q = readInt()
qa = []
booh = 0
for i in range(q):
	x = input()
	if x=="1":
		qa.append([1,0,0])
	else:
		x = x.split()
		qa.append([int(x[0]),int(x[1]),x[2]])

def t1(s):
	return s[::-1]

def t2(f,c,s):
	if f==1:
		return c+s
	else:
		return s+c

fi=""
la=""
for a in qa:
	if a[0]==1:
		booh = (booh+1)%2
	else:
		if (a[1]+booh)%2==1:
			fi=a[2]+fi
		else:
			la+=a[2]

s = fi+s+la
if booh==1:
	s = t1(s)

print(s)
### BUGGY CODE ###

# import numpy as np
import math
import sys
input = sys.stdin.readline

X = int(input())

if X == 2:
    print(X)
    sys.exit()

if X == 3:
    print(X)
    sys.exit()

if (X == 4) | (X == 5):
    print(5)
    sys.exit()

if X % 2 == 0:
    X += 1

while True:
    isNotPrime = False
    temp = pow(2,X-1,X)
    if temp == 1:
        if (X % 6 != 1) & (X % 6 != 5):
            X += 2
            continue
        for i in range(3,int(math.sqrt(X))+1,2):
            if X % i == 0:
                isNotPrime = True
            if isNotPrime:
                break
        if isNotPrime == False:
            break
    else:
        X += 2

print(X)


### FIXED CODE ###

# import numpy as np
import math
import sys
input = sys.stdin.readline

X = int(input())

if X == 2:
    print(X)
    sys.exit()

def segment_sieve(a,b):
    ass = []
    is_prime_small = [True] * (int(b**0.5)+1)
    is_prime = [True] * (b-a)
    for i in range(2,int(b**0.5)):
        if is_prime_small[i]:
            j = 2*i
            while j**2 < b:
                is_prime_small[j] = False
                j += i
            j = max(2*i,((a+i-1)//i)*i)
            while j < b:
                is_prime[j-a] = False
                j += i
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(a+i)
    if ass[0] == 1:
        del ass[0]
    return ass

list = segment_sieve(X,100004)
res = list[0]

print(res)
### BUGGY CODE ###

n=int(input())
cnt=0
for b in range(1,n):
    for c in range(1,n):
        if (n-c)%b==0:
            cnt+=1
            # print(b,c)
        elif (n-c)/b<1:
            break
print(cnt)

### FIXED CODE ###

n=int(input())
cnt=0

for b in range(1,n):
    cnt+=int((n-1)/b)

print(cnt)
### BUGGY CODE ###

import itertools
n=int(input())
l=list(map(int,input().split()))


def triangle(num):
    a,b,c=num
    if a<(b+c) and b<(a+c) and c<(a+b):
        return True
    else:
        return False
ans=0
for num in itertools.combinations(l,3):
    ans+=triangle(num)
print(ans)


### FIXED CODE ###

from bisect import bisect_left
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):
        ans+=max(0,bisect_left(l, l[a] + l[b])-b-1)
        
        
print(ans)
### BUGGY CODE ###

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

    N = int(input())
    # 1-indexed
    A = [deque() for _ in range(N+1)]
    # O(N^2)
    for i in range(1,N+1):
        for j in input().split():
            A[i].append(int(j))

    # O(N)
    def is_not_empty():
        for x in A:
            if x:
                return True
        return False

    answer = 0
    while is_not_empty():
        played = set()
        for i in range(1,N+1):
            if i in played:
                continue
            if not A[i]:
                continue
            enemy = A[i].popleft()
            ME = A[enemy].popleft()
            if ME == i and not(enemy in played):
                played.add(ME)
                played.add(enemy)
            else:
                A[i].appendleft(enemy)
                A[enemy].appendleft(ME)
        if len(played) == 0:
            print(-1)
            exit()
        answer += 1

    print(answer)

if __name__ == '__main__':
    main()

### FIXED CODE ###

# O(N)
def is_not_empty(A):
    for x in A:
        if x:
            return True
    return False

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

    N = int(input())
    # 1-indexed
    A = [deque() for _ in range(N+1)]
    # O(N^2)
    for i in range(1,N+1):
        for j in input().split():
            A[i].append(int(j))

    # 当日の参加者
    today = set()
    # 初日
    for i in range(1,N+1):
        # 既に参加した人はダメ
        if i in today:
            continue
        enemy = A[i].popleft()
        ME = A[enemy].popleft()
        if ME == i and not(enemy in today):
            today.add(ME)
            today.add(enemy)
        else:
            A[i].appendleft(enemy)
            A[enemy].appendleft(ME)
    # 初日に誰も試合できなかったとき
    if not today:
        print(-1)
        exit()

    # 前日の参加者
    yesterday = today
    # 日数
    answer = 1
    while is_not_empty(A):
        today = set()
        # 前日に試合した人は必ず次の日に試合する
        for i in yesterday:
            if not A[i]:
                continue
            if i in today:
                continue
            enemy = A[i].popleft()
            ME = A[enemy].popleft()
            if ME == i and not(enemy in today):
                today.add(ME)
                today.add(enemy)
            else:
                A[i].appendleft(enemy)
                A[enemy].appendleft(ME)
        if not today:
            print(-1)
            exit()
        answer += 1
        yesterday = today

    print(answer)

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

import sys
input=sys.stdin.readline
n,q=map(int,input().split())
s=input()
a=[]
for x in range(n-1):
  if s[x]=='A' and s[x+1]=='C':
    a.append(x)
    
for y in range(q):
  ans=0
  l,r=map(int,input().split())
  ans+=sum(1 for i in a if i>=l-1 and i<=r-2)
  print(ans)



### FIXED CODE ###

import sys
input=sys.stdin.readline
n,q=map(int,input().split())
s=input()
a=[0]*n
for x in range(1,n):
  a[x]+=a[x-1]
  if s[x-1]=='A' and s[x]=='C':
    a[x]+=1
  
    
for y in range(q):
  
  l,r=map(int,input().split())
  ans=a[r-1]-a[l-1]
  print(ans)
### BUGGY CODE ###

from collections import defaultdict as ddict

n=int(input())
a=[]
dict={}
for i in range(n):
    d=ddict(int)
    s=input()
    for x in s:
        d[x]+=1
    a.append(sorted(d.items()))
#print(a)

count=0
for i in range(n):
    temp=a.pop()
    if temp in a:
        count+=a.count(temp)
print(count)

### FIXED CODE ###

from collections import Counter
n=int(input())
d=Counter()
ans=0
for i in range(n):
    t=str("".join(sorted(input())))
    if t in d:
        ans+=d[t]
    d[t]+=1
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))
def f(n):
    return (n+1)/2
a=[]
for i in range(N-K+1):
    a.append(sum([f(p[j]) for j in range(i, i+K)]))
print(max(a))

### FIXED CODE ###

from itertools import accumulate
N, K = map(int, input().split())
P = list(map(int, input().split()))
P = [0]+[(p+1)/2 for p in P]
S = list(accumulate(P))
B = []
for j in range(N-K+1):
    B.append(S[j+K]-S[j])
ans = max(B)
print(ans)
### BUGGY CODE ###

MOD = 10**9 + 7

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

res = 0

for i in range(N)[:-1]:
  for j in range(N)[i+1:]:
    res += A[i] * A[j]
    res %= MOD

print(res)

### FIXED CODE ###

MOD = 10**9 + 7

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

res = 0
sumA = sum(A)
for i in range(N)[:-1]:
  sumA -= A[i]
  res += A[i] * sumA
  res %= MOD

print(res)
### BUGGY CODE ###

K = int(input())
dic = {}
def mygcd(x, y):
    if (x, y) in dic:
        return dic[(x, y)]
    if y == 0:
        dic[(x, y)] = x
        return x
    else:
        res = mygcd(y, x % y) #再帰定義
        dic[(x, y)] = res
        return res
ans = 0
for i in range(K, 0, -1):
    for j in range(K, 0, -1):
        tmp_gcd = mygcd(i, j)
        for k in range(K, 0, -1):
            ans += mygcd(tmp_gcd, k)
print(ans)      

### FIXED CODE ###

import math
K = int(input())
ans = 0
for i in range(1, K + 1):
    for j in range(i, K + 1):
        for k in range(j, K + 1):
            tmp_gcd = math.gcd(i, j)
            tmp_gcd = math.gcd(tmp_gcd, k)
            if i == j == k:
                ans += tmp_gcd
            elif i == j or i == k or j == k:
                ans += tmp_gcd * 3
            else:
                ans += tmp_gcd * 6
print(ans)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()

for i in range(q):
    n_, q_ = map(int, input().split())
    s_ = s[n_-1:q_]
    l_ = s_.count("AC")
    print(l_)


### FIXED CODE ###

n, q = map(int, input().split())
s = input()
flag = False
count = 0
li = []

for i in range(n):
    if s[i] == "A":
        flag = True
    elif s[i] == "C" and flag is True:
        count += 1
        flag = False
    else:
        flag = False
    li.append(count)

for i in range(q):
    l, r = map(int, input().split())
    print(li[r-1] - li[l-1])
### BUGGY CODE ###

from itertools import accumulate
N, M, K = map(int, input().split())
A = [0] + list(map(int, input().split()))
B = [0] + list(map(int, input().split()))
A = list(accumulate(A))
B = list(accumulate(B))
ans = 0
for n in range(N+1):
    for m in reversed(range(M+1)):
        if A[n] + B[m] <= K:
            ans = max(ans, n+m)
            break
print(ans)

### FIXED CODE ###

import itertools
N,M,K = map(int,input().split())
A = [0]+list(map(int,input().split()))
B = [0]+list(map(int,input().split()))
SA = list(itertools.accumulate(A))
SB = list(itertools.accumulate(B))
ans = 0
j = len(B)-1
for i in range(len(SA)):
    while(j>=0):
        if SA[i] + SB[j] <= K:
            ans = max(ans,i+j)
            break
        j-=1
print (ans)
### BUGGY CODE ###

N = int(input())
S = input()
L = []
Ans = 0
for i in range(N):
  s = S[i]
  a = 0
  b = 0
  for j in range(i+1,N):
    t = S[j]
    if s != t:
      K = ["R","G","B"]
      K.remove(s)
      if t == K[0]:
        a +=1
      else:
        b +=1
  Ans += a*b

for i in range(N):
  for j in range(i+1,N):
    k = 2*j-i
    if j < k <= N-1:
      if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
        Ans -=1
print(Ans)

### FIXED CODE ###

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

L = [0,0,0]
for i in range(N):
    if S[i] == "R":
        L[0] +=1
    elif S[i] == "G":
        L[1] +=1
    else:
        L[2] +=1

Ans = L[0]*L[1]*L[2]

for i in range(N):
  s = S[i]
  n = min(N, (N+i)//2 + 1)
  for j in range(i+1,n):
    t = S[j]
    if s != t:
      k = 2*j-i
      if k <= N-1:
        u = S[k]
        if t != u and u != s:
          Ans -=1
print(Ans)