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

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w = list(map(int, input().split()))
a = [None]*h
for i in range(h):
    a[i] = input()
    if "S" in a[i]:
        start = (i*w+a[i].index("S"))
    if "T" in a[i]:
        goal = (i*w+a[i].index("T"))
if start%w==goal%w or start//w==goal//w:
    val = -1
else:
    import scipy.sparse
    data = []
    rs = []
    cs = []
    def append(u,v):
        data.append(1)
        rs.append(u)
        cs.append(v)
        
    for i in range(h*w):
        if i not in (start, goal):
            append(2*i, 2*i+1)
    start = start*2+1
    goal = goal*2
    def add(i0,j0,i1,j1):
        u = i0*w+j0
        v = i1*w+j1
        append(2*u+1, 2*v)
#         append(2*v+1, 2*u)
    for i in range(h):
        index = []
        for j in range(w):
            if a[i][j] in ("o", "S", "T"):
                index.append(j)
        for x in index:
            for y in index:
                if x!=y:
                    add(i,x,i,y)
    for j in range(w):
        index = []
        for i in range(h):
            if a[i][j] in ("o", "S", "T"):
                index.append(i)
        for x in index:
            for y in index:
                if x!=y:
                    add(x,j,y,j)
    m = scipy.sparse.csr_matrix((data, (rs, cs)), shape=(2*h*w, 2*h*w))
    val = scipy.sparse.csgraph.maximum_flow(m, start, goal).flow_value # startからの最短路木を求める
print(val)

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w = list(map(int, input().split()))
data= []
rs = []
cs = []
for i in range(h):
    c = input()
    if "S" in c:
        start = (i, c.index("S"))
    if "T" in c:
        goal = (i, c.index("T"))
    for j in range(w):
        if c[j] in ("o"):#, "S", "T"):
            data.append(1)
            rs.append(i)
            cs.append(h+j)
            data.append(1)
            rs.append(h+j)
            cs.append(i)
s = h+w
t = h+w+1
V = 10**9
data.append(V)
rs.append(s)
cs.append(start[0])
data.append(V)
rs.append(start[0])
cs.append(s)

data.append(V)
rs.append(s)
cs.append(start[1]+h)
data.append(V)
rs.append(start[1]+h)
cs.append(s)

data.append(V)
rs.append(goal[0])
cs.append(t)
data.append(V)
rs.append(t)
cs.append(goal[0])

data.append(V)
rs.append(t)
cs.append(goal[1]+h)
data.append(V)
rs.append(goal[1]+h)
cs.append(t)

import scipy.sparse
m = scipy.sparse.csr_matrix((data, (rs, cs)), shape=(h+w+2,h+w+2))
val = scipy.sparse.csgraph.maximum_flow(m, s, t).flow_value
if val>=10**9:
    val = -1
print(val)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
x = 1
for i in a:
    x *= i
print(-1 if x > 10**18 else x)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
if 0 in a:
    print(0)
    exit()
x = 1
for i in a:
    x *= i
    if x > 10**18:
        print(-1)
        exit()
print(x)
### BUGGY CODE ###

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

import numpy as np
N,T=map(int, input().split())
val=[list(map(int, input().split())) for i in range(N)]
val=np.array(val)
index=np.argsort(val[:,0])
A=val[index,0]
B=val[index,1]

temp=[[0]*N for i in range(T+1)]
for itemp in range(T):
    i=itemp
    if i>=A[0]:
        temp[i][0]=B[0]
    for jtemp in range(N-1):
        j=jtemp+1
        if i>0:
            temp[i][j]=max(temp[i][j],temp[i-1][j])
            
        temp[i][j]=max(temp[i][j],temp[i][j-1])
        if A[j]<T-i:
            temp[i+A[j]][j]=max(temp[i][j-1]+B[j],temp[i+A[j]][j])
        else:
            temp[T][j]=max(temp[i][j-1]+B[j],temp[T][j])
print(max(temp[-1][:])) 

### FIXED CODE ###

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

N,T=map(int, input().split())
val=[list(map(int, input().split())) for i in range(N)]

#import sys
#input = sys.stdin.readline
#val = list(input()) #abc
#val=np.array(val)
#index=np.argsort(val[:,0])
#A=val[index,0].tolist()
#B=val[index,1].tolist()
val.sort()
A=[v[0] for v in val]
B=[v[1] for v in val]

#temp=np.zeros((T+1,N))
#Ts=T*np.ones(N-1)
#jun=np.arange(1,N)
#for itemp in range(T):
#    i=itemp
#    if i>=A[0]:
#        temp[i,0]=B[0]
#    if i>0:
#        temp[i,:]=np.amax([temp[i,:],temp[i-1,:]],0)
#    for jtemp in range(N-1):
#        j=jtemp+1
#        temp[i,j]=max(temp[i,j],temp[i,j-1])
#    jnext=np.amin([Ts,i+A[1:]],0)
#    jnext=[int(s) for s in jnext]
#    temp[jnext,jun]=np.amax([temp[i,:-1]+B[1:],temp[jnext,jun]],0)

temp=[[0]*N for i in range(T+1)]

for itemp in range(T):
    i=itemp
    if i>=A[0]:
        temp[i][0]=B[0]
    for jtemp in range(N-1):
        j=jtemp+1
        jbfo=temp[i][j-1]
        ijnow=temp[i][j]
        
        if i>0:
            temp[i][j]=max(ijnow,temp[i-1][j])
            
        temp[i][j]=max(ijnow,jbfo)
        if A[j]<T-i:
            temp[i+A[j]][j]=max(jbfo+B[j],temp[i+A[j]][j])
        else:
            temp[T][j]=max(jbfo+B[j],temp[T][j])
print(int(max(temp[-1][:])))
### BUGGY CODE ###

from collections import deque

S = deque(input())
Q = int(input())

for _ in range(Q):
  q = input()
  
  if q[0] == "1":
    S.reverse()
  
  if q[0] == "2":
    if q[2] == "1":
      S.appendleft(q[4])
    else:
      S.append(q[4])

print("".join(S))

### FIXED CODE ###

from collections import deque

S = deque(input())
Q = int(input())
Flag = 1

for _ in range(Q):
  q = input()
  
  if q[0] == "1":
    Flag *= -1
  
  if q[0] == "2":
    if Flag > 0:
      if q[2] == "1":
        S.appendleft(q[4])
      else:
        S.append(q[4])
    else:
      if q[2] == "1":
        S.append(q[4])
      else:
        S.appendleft(q[4])
  
if Flag < 0:
  S.reverse()

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

n=int(input())
a=list(map(int,input().split()))
count=0
while len(a)>=2:
    if a[0]>a[1]:
        count+=a[0]-a[1]
        w=a[0]
        a.pop(0)
        a[0]=w
    else:
        a.pop(0)
print(count)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
count=0
ma=a[0]
for i in range(1,len(a)):
    if a[i]<ma:
        count+=ma-a[i]
    else:
        ma=a[i]
print(count)
### BUGGY CODE ###

def sieve(n):
    tmp=[i for i in range(n, 1, -1)]
    s=[]
    while len(tmp)>0:
        p=tmp.pop()
        s.append(p)
        for i in range(len(tmp), 0, -1):
            if tmp[-i]%p==0:
                del tmp[-i]
    return s

naturals=sieve(100000)

q=int(input())
for _ in range(q):
    left, right=map(int,input().split())
    count=0
    for i in range(left, right+1):
        if i==1 or i%2==0:
            continue
        if i in naturals and int((i+1)/2) in naturals:
            count+=1
    print(count)

### FIXED CODE ###

def get_isPrime(n):         #1~nまでの数で、素数は1、それ以外は0となるようなリストを返す
    isprime=[1]*(n+1)
    isprime[0]=0
    isprime[1]=0
    for i in range(2, int(n**0.5)+1):
        if not isprime[i]:
            continue
        for j in range(i*2, n+1, i):
            isprime[j]=0
    return isprime

max_n=100000
isprime=get_isPrime(max_n)

ruiseki=[]
for i in range(max_n+1):
    if i==0 or i==1 or i==2:
        ruiseki.append(0)
    else:
        if i%2==0:
            ruiseki.append(ruiseki[i-1])
        else:
            if isprime[i] and isprime[int((i+1)/2)]:
                ruiseki.append(ruiseki[i-1]+1)
            else:
                ruiseki.append(ruiseki[i-1])

q=int(input())
for _ in range(q):
    left, right=map(int,input().split())
    print(ruiseki[right]-ruiseki[left-1])
### BUGGY CODE ###

n, m = map(int, input().split())
baitos = [list(map(int, (input().split()))) for _ in range(n)]
baitos = sorted(baitos, key=(lambda x: x[0]))

max = 0
available_works = []
for shigotobi in reversed(range(m)):
    nokori = m-shigotobi
    #kuwaeru
    for baito_index in range(len(baitos)):
        if baitos[baito_index][0] <= nokori:
            available_works.append(baitos[baito_index])
        else:
            baitos = baitos[baito_index:]
            break

    #itibanniiyatu
    max_now = 0
    max_index = None

    for work_index in range(len(available_works)):
        if available_works[work_index][1] >= max_now:
            max_index = work_index
            max_now = available_works[max_index][1]

    if max_index is not None:
        max += max_now
        available_works.pop(max_index)
        max_index = None

print(max)

### FIXED CODE ###

from collections import defaultdict
from heapq import heappush, heappop
n, m = map(int, input().split())
baito_dict = defaultdict(list)
for _ in range(n):
    day, weight = map(int, input().split())
    baito_dict[day].append(weight)


max = 0

available_works = []

for day in range(1, m+1):
    for weight in baito_dict[day]:
        heappush(available_works, -weight)
    if available_works:
        max += heappop(available_works)

print(-max)
### BUGGY CODE ###

k, s = map(int, input().split())
count = 0
for i in range(k+1):
  if(i>s):
    break
  for j in range(k+1):
    if(i+j>s):
      break
    for c in range(k+1):
      if(i + j + c == s):
        count += 1
print(count)

### FIXED CODE ###

k, s = map(int, input().split())
count = 0
for i in range(k+1):
  for j in range(k+1):
    if(0 <= s-i-j and s-i-j <= k):
      count += 1
print(count)
### BUGGY CODE ###

N = int(input())
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)
# C.append(-1)
a_count = [0 for i in range(N)]
b_count = [0 for i in range(N)]
# i, j = 0, 0
# while i < N:
#     if B[i] >= C[j]:
#         b_count[i] = j
#         i += 1
#     else:
#         j += 1
for i in range(N):
    for j in range(N):
        if B[i] < C[j]:
            b_count[i] += 1
for i in range(N):
    for j in range(N):
        if A[i] < B[j]:
            a_count[i] += b_count[j]
print(sum(a_count))

### FIXED CODE ###

N = int(input())
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)
c_cnt = [1 for i in range(N)]

def count(A, B, b_cnt):
    B.append(-1)
    a_cnt = [0 for i in range(N)]
    i, j = 0, 0
    while i < N:
        if A[i] < B[j]:
            a_cnt[i] += b_cnt[j]
            j += 1
        else:
            i += 1
            if 1 <= i < N:
                a_cnt[i] = a_cnt[i-1]
    return a_cnt

b_cnt = count(B, C, c_cnt)
a_cnt = count(A, B, b_cnt)
print(sum(a_cnt))
### BUGGY CODE ###

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

N = int(input())
A = list(map(int, input().split()))
B = A[:]
B.sort()
C = [B[0]]
D = [1]
L = 0
for i in range(N-1):
    if B[i] == B[i+1]:
        D[L] += 1
    else:
        C.append(B[i+1])
        D.append(1)
        L += 1

E = []

for i in range(len(C)):
    t = 0
    for j in range(len(C)):
        if i == j and D[j]>2:
            t += cmb(D[j]-1,2)
        if i != j and D[j]>1:
            t += cmb(D[j],2)
    E.append(t)
for i in range(N):
    print(E[C.index(A[i])])

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
C = {}
for i in A:
    if i in C.keys():
        C[i] += 1
    else:
        C[i] = 1

total = 0

for i in C.keys():
   if C[i]>1:
        total += (C[i]*(C[i]-1))//2

for i in A:
    print(total-(C[i]-1))
### BUGGY CODE ###

import bisect
N=int(input())

que=[-1]
for i in range(N):
    a=int(input())
    
    if que[0]<a:
        i=bisect.bisect_left(que, a)
        que[i-1]=a
    else:
        que=[a]+que

print(len(que))
#print(que)

### FIXED CODE ###

import bisect
from collections import deque
N=int(input())

que=deque([-1])
for i in range(N):
    a=int(input())
    
    if que[0]<a:
        i=bisect.bisect_left(que, a)
        que[i-1]=a
    else:
        que.appendleft(a)

print(len(que))
#print(que)
### BUGGY CODE ###

# 解説を参考に作成
def solve():
    S = input()
    lenS = len(S)
    mod_list = [0] * 2019
    Si = 0
    for i in range(lenS):
        Si += 10 ** i * int(S[lenS - 1 - i])
        x = Si % 2019
        mod_list[x] += 1
    result = 0
    for i, ml in enumerate(mod_list):
        if i == 0:
            result += ml
        result += int(ml * (ml - 1) / 2)
    print(result)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

# 解説を参考に作成
# さらに 提出 #12403542 を参考


def solve():
    S = input()
    lenS = len(S)
    mod_list = [0] * 2019
    x = 0
    for i in range(lenS):
        x = (int(S[lenS - 1 - i]) * pow(10, i, 2019) + x) % 2019
        mod_list[x] += 1

    result = 0
    for i, ml in enumerate(mod_list):
        if i == 0:
            result += ml
        result += int(ml * (ml - 1) / 2)
    print(result)


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

n, k = map(int, input().split())
a_list = [int(input()) for _ in range(n)]

dp = [1] * n

for i in range(n):
    for j in range(max(0, i - 1000), i):
        if abs(a_list[i] - a_list[j]) <= k:
            dp[i] = max(dp[i], dp[j] + 1)

ans = max(dp)
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
a_list = [int(input()) for _ in range(n)]

dp = [1] * n

for i in range(n):
    for j in range(max(0, i - 100), i):
        if abs(a_list[i] - a_list[j]) <= k:
            dp[i] = max(dp[i], dp[j] + 1)

ans = max(dp)
print(ans)
### BUGGY CODE ###

s = list(input())
s_len = len(s)

to_l = [0] * s_len
to_r = [0] * s_len
ans = [0] * s_len
cnt = 0
for i, c in enumerate(s):
    if c == 'R':
        cnt = 0
    else:
        cnt += 1
    to_r[i] = cnt

cnt = 0
for i,c in enumerate(reversed(s)):
    if c == 'L':
        cnt = 0
    else:
        cnt += 1
    to_l[s_len-i-1] = cnt

for i in range(s_len):
    c = s[i]
    if c == 'R':
        d = to_l[i]
    else:
        d = to_r[i]

    if d % 2 == 0:
        to_d = d
    else:
        to_d = d - 1

    if c == 'R':
        to_i = i + to_d
    else:
        to_i = i - to_d
    
    if to_i < 0 or s_len <= to_i:
        pass
    else:
        ans[to_i] += 1

ans_s = str(ans[0])
for cnt in ans[1:]:
    ans_s += (" " + str(cnt))
print(ans_s)


### FIXED CODE ###

s = input()
s_len = len(s)

to_l = [0] * s_len
to_r = [0] * s_len
ans = [0] * s_len
cnt = 0
for i, c in enumerate(s):
    if c == 'R':
        cnt = 0
    else:
        cnt += 1
    to_r[i] = cnt

cnt = 0
for i,c in enumerate(reversed(s)):
    if c == 'L':
        cnt = 0
    else:
        cnt += 1
    to_l[s_len-i-1] = cnt

for i in range(s_len):
    c = s[i]
    if c == 'R':
        d = to_l[i]
    else:
        d = to_r[i]

    if d % 2 == 0:
        to_d = d
    else:
        to_d = d - 1

    if c == 'R':
        to_i = i + to_d
    else:
        to_i = i - to_d
    
    if to_i < 0 or s_len <= to_i:
        pass
    else:
        ans[to_i] += 1

#ans_s = str(ans[0])
#for cnt in ans[1:]:
#    ans_s += (" " + str(cnt))
#print(ans_s)
for i in ans:
    print(i)
### BUGGY CODE ###

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

for i in range(N):
    tmp = X_list.copy()
    tmp.pop(i)
    tmp.sort()
    print(tmp[int(N/2)-1])

### FIXED CODE ###

N = int(input())
X_list = list(map(int, input().split()))
tmp = X_list.copy()

tmp.sort()
a = tmp[int(N/2)-1]
b = tmp[int(N/2)]
for i in range(N):
    if(X_list[i] <= a):
        print(b)
    else:
        print(a)
### BUGGY CODE ###

N = int(input())
S = list(input())
count = 3 * 10 ** 5
for i in range(N):
    count_tmp = 0
    for j in range(N):
        if j < i:
            if S[j] != "E":
                count_tmp += 1
        elif j > i:
            if S[j] != "W":
                count_tmp += 1
    count = min(count, count_tmp)
print(count)

### FIXED CODE ###

N = int(input())
S = input()
ans = cnt = S[1:].count("E")
for i in range(1, N):
    if S[i] == "E":
        cnt -= 1
    if S[i - 1] == "W":
        cnt += 1
    ans = min(ans, cnt)
print(ans)
### BUGGY CODE ###

N, Q = [int(i) for i in input().split()]
S = input()
l, r = [[None] * Q for _ in range(2)]
for i in range(Q):
  l[i], r[i] = [int(i) for i in input().split()]
  
for i in range(Q):
  s = S[l[i]-1:r[i]]
  
  count = 0
  i = s.find('AC')
  while i >= 0:
    count += 1
    i = s.find('AC', i+2)
  
  print(count)

### FIXED CODE ###

import sys
def input():
	return sys.stdin.readline()

N, Q = map(int, input().split())
S = input()
p = []
for _ in range(Q):
	p.append(tuple([int(_)-1 for _ in input().split()]))

L = [0] * N
l = 0

for i in range(N-1):
	if S[i] == 'A' and S[i+1] == 'C':
		l += 1
	L[i] = l

for i in range(Q):
	print(L[p[i][1]-1] - L[p[i][0]-1])
### BUGGY CODE ###

#pypyは内包表記使わない, rstrip注意
#提出前に見返すこと！
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    inf = 10**17
    #mod = 1000000007

    N = int(input())
    dp = [inf]*(N+1)
    dp[0] = 0
    money = [1, 6, 9, 36, 81, 216, 729, 6**4, 6561, 6**5, 6**6, 59049]
    while dp[N]==inf:
        for i in range(N, 0, -1):
            for j in money:
                if i<j:
                    continue
                dp[i] = min(dp[i-j]+1, dp[i])
    print(dp[N])

if __name__ == '__main__':
    main()

### FIXED CODE ###

#pypyは内包表記使わない, rstrip注意
#提出前に見返すこと！
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    inf = 10**17
    #mod = 1000000007

    N = int(input())
    dp = [inf]*(N+1)
    dp[0] = 0
    money = [1, 6, 9, 36, 81, 216, 729, 6**4, 6561, 6**5, 6**6, 59049]
    while dp[N]==inf:
        for i in range(N, 0, -1):
            for j in money:
                if i<j:
                    continue
                dp[i] = min(dp[i-j]+1, dp[i])
    print(dp[N])

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

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

cnt = 1
if n==1:
    print(cnt)
else:
    for i in range(1,n):
        if min(p[:i+1])==p[i]:
            cnt +=1
    print(cnt)


### FIXED CODE ###

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

minp =[p[0]]

for i in range(1,n):
    minp.append(min(minp[i-1],p[i]))


cnt = 0
for i in range(n):
    if minp[i] == p[i]:
        cnt += 1
print(cnt)
### BUGGY CODE ###

s = input()
ans = 0
def united(stri):
    for a in stri:
        if a != stri[0]:
            return False
    return True

while (not united(s)) and len(s) >= 2:
    k = len(s)
    if k == 2:
        if s[0] != s[1]:
            ans += 2
        break
    for i in range(0,k-1):
        if s[i] != s[i+1]:
            if i == k - 2:
                s = s[:i]
            elif i == 0:
                s = s[i+2:]
            else:
                s = s[:i] + s[i+2:]
            ans += 2
            break
print(ans)

### FIXED CODE ###

s = input()
c_0 = 0
c_1 = 0
for i in s:
    if i == "0":
        c_0 += 1
    elif i == "1":
        c_1 += 1
print(min(c_0,c_1)*2)
### BUGGY CODE ###

n = int(input())
b = list(map(int, input().split()))
x = 0

for i in range(n):
  if (i+1) in b:
    print(b.count(i+1))
  else:
    print(0)

### FIXED CODE ###

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

c = collections.Counter(a)
for i in range(n):
  print(c[i+1])
### BUGGY CODE ###

S = input()
Slength = len(S)

def remove01(preS):
    return "".join(preS.split('01'))

def remove10(preS):
    return "".join(preS.split('10'))



while True:
    T = remove10(remove01(S))

    if T == S:
        break
    else:
        S = T
    

print(Slength-len(T))

### FIXED CODE ###

S = input()

print(min(S.count("0"), S.count("1"))*2)
### BUGGY CODE ###

from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import Counter
from pprint import pprint

def myinput():
    return map(int,input().split())

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

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

r = []
g = []
b = []
for i in range(n):
    if s[i]=="R":
        r.append(i)
    elif s[i]=="G":
        g.append(i)
    elif s[i]=="B":
        b.append(i)
    else:
        pass
# print(r,g,b)
count = 0
for i in r:
    for j in g:
        for k in b:
            a = [i,j,k]
            a.sort()
            if (a[1]-a[0])!=(a[2]-a[1]):
                count += 1
print(count)

### FIXED CODE ###

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

r = []
g = []
b = []
for i in range(n):
    if s[i]=="R":
        r.append(i)
    elif s[i]=="G":
        g.append(i)
    elif s[i]=="B":
        b.append(i)
    else:
        pass
# print(r,g,b)
count = 0
for i in range(n):
    x = s[i]
    for sa in range(n):
        j = i + sa
        k = j + sa
        if j<n:
            y = s[j]
        else:
            break
        if k<n:
            z = s[k]
        else:
            break
        if x!=y and y!=z and z!=x:
            count += 1
# print(count)
ans = len(r) * len(g) * len(b) - count
print(ans)
### BUGGY CODE ###

L, R = [int(i) for i in input().split()]
R = min(R, L + 4038)
diff = R - L
ans = 2018
for i in range(L, R + 1):
    for j in range(i + 1, R + 1):
        x = i * j % 2019
        ans = min(ans, x)
print(ans)


### FIXED CODE ###

L, R = [int(i) for i in input().split()]
R = min(R, L + 4038)
ans = 2018
for i in range(L, R + 1):
    for j in range(i + 1, R + 1):
        x = (i * j) % 2019
        if x == 0:
            ans = 0
            break
        ans = min(ans, x)
print(ans)
### BUGGY CODE ###

def main():
  import sys
  from numpy import zeros
  input=sys.stdin.buffer.readline
  n=int(input())+1
  data=zeros((n*2,26),int)
  def update(i,x):
    i+=n
    data[i]=0
    data[i,x]=1
    i//=2
    while i:
      data[i]=data[i*2]|data[i*2+1]
      i//=2
  def query(l,r):
    l+=n
    r+=n
    s=zeros(26,int)
    while l<r:
      if l&1:
        s|=data[l]
        l+=1
      if r&1:
        r-=1
        s|=data[r]
      l//=2
      r//=2
    return s.sum()
  for i,c in enumerate(input()[:-1],n):data[i,c-97]=1
  for i in range(n-1,0,-1):data[i]=data[i*2]|data[i-~i]
  s=[]
  for _ in range(int(input())):
    q,a,b=input().split()
    if q[0]>49:s+=query(int(a)-1,int(b)),
    else:update(int(a)-1,b[0]-97)
  print('\n'.join(map(str,s)))
main()

### FIXED CODE ###

import sys
input=sys.stdin.buffer.readline
n=int(input())+1
data=[0]*n*2
def update(i,x):
  i+=n
  data[i]=x
  i//=2
  while i:
    data[i]=data[i*2]|data[i*2+1]
    i//=2
def query(l,r):
  l+=n
  r+=n
  s=0
  while l<r:
    if l&1:
      s|=data[l]
      l+=1
    if r&1:
      r-=1
      s|=data[r]
    l//=2
    r//=2
  return sum(map(int,bin(s)[2:]))
for i,c in enumerate(input()[:-1]):
  update(i,2**(c-97))
for _ in range(int(input())):
  q,a,b=input().split()
  if q[0]>49:print(query(int(a)-1,int(b)))
  else:update(int(a)-1,2**(b[0]-97))