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

s=input()

lens = len(s)
logs = lens.bit_length()
doubling = [[0]*lens for _ in range(logs)]

for i in range(lens):
  if s[i] == 'R':
    doubling[0][i] = i + 1
  else:
    doubling[0][i] = i - 1

for i in range(1,logs):
  for j in range(lens):
    doubling[i][j] = doubling[i-1][doubling[i-1][j]]

for i in range(lens):
  print(doubling[logs-1].count(i))


### FIXED CODE ###

s=input()

logk = (10**100).bit_length()
lens = len(s)
logs = lens.bit_length()
doubling = [[0]*lens for _ in range(logk)]

for i in range(lens):
  if s[i] == 'R':
    doubling[0][i] = i + 1
  else:
    doubling[0][i] = i - 1

for i in range(1,logk):
  for j in range(lens):
    doubling[i][j] = doubling[i-1][doubling[i-1][j]]

from collections import Counter
result = Counter(doubling[logk-1])
for i in range(lens):
  print(result[i])
### BUGGY CODE ###

import sys
from collections import *

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(u=0):
        if not to[u]:
            dp[u].append([inv2, inv2, 0])
            return
        dpu = []
        for v in to[u]:
            dfs(v)
            v = utou[v]
            if not dpu:
                dpu = dp[v]
                utou[u] = v
                continue
            dpv = dp[v]
            if len(dpu) < len(dpv):
                dpu, dpv = dpv, dpu
                utou[u] = v
            for d in range(len(dpv)):
                dpu[d][2] = (dpu[d][2] * sum(dpv[d]) + dpv[d][2] * sum(dpu[d])
                             - dpu[d][2] * dpv[d][2] + dpu[d][1] * dpv[d][1]) % md
                dpu[d][1] = (dpu[d][0] * dpv[d][1] + dpu[d][1] * dpv[d][0]) % md
                dpu[d][0] = (dpu[d][0] * dpv[d][0]) % md
        for d in range(len(dpu)):
            dpu[d][0] = (dpu[d][0] + dpu[d][2]) % md
            dpu[d][2] = 0
        dpu.appendleft([inv2, inv2, 0])

    md = 10 ** 9 + 7
    inv2 = pow(2, md - 2, md)
    to = defaultdict(list)
    n = int(input())
    pp = list(map(int, input().split()))
    for i, p in enumerate(pp):
        i += 1
        to[p].append(i)
    #print(to)
    utou = list(range(n + 1))
    dp = [deque() for _ in range(n + 1)]
    dfs()
    #p2D(dp)
    # print(utou)
    root = utou[0]
    ans = 0
    for dpr in dp[root]:
        ans += dpr[1]
    ans %= md
    print((ans * pow(2, n + 1, md)) % md)

main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(u=0):
        def merge(dpu, dpv):
            vn = len(dpv)
            for d in range(-1, -1 - vn, -1):
                u0, u1, u2 = dpu[d]
                v0, v1, v2 = dpv[d]
                n0 = (u0 * v0) % md
                n1 = (u0 * v1 + u1 * v0) % md
                n2 = (u2 * (v0 + v1 + v2) + v2 * (u0 + u1) + u1 * v1) % md
                dpu[d] = (n0, n1, n2)

        # 葉の場合
        if len(to[u]) == 0:
            return [(inv2, inv2, 0)]
        # すべての子をマージ
        dpu = []
        mxlen=0
        for v in to[u]:
            dpv = dfs(v)
            #深さが2段以上あったらu2をu0に
            if not dpu:
                dpu = dpv
            else:
                if len(dpu) < len(dpv): dpu, dpv = dpv, dpu
                mxlen=max(mxlen,len(dpv))
                merge(dpu, dpv)
        for d in range(-1,-1-mxlen,-1):
            u0,u1,u2=dpu[d]
            dpu[d] = (u0 + u2, u1, 0)
        dpu.append((inv2, inv2, 0))
        return dpu

    md = 10 ** 9 + 7
    # 1/2のmod
    inv2 = pow(2, md - 2, md)
    n = int(input())
    to = [[] for _ in range(n+1)]
    pp = list(map(int, input().split()))
    for i, p in enumerate(pp, 1):
        to[p].append(i)
    # print(to)
    dp0 = dfs()
    # print(dp0)
    ans = sum(u1 for _, u1, _ in dp0)
    print((ans * pow(2, n + 1, md)) % md)

main()
### BUGGY CODE ###

r, g, b, n = map(int, input().split())

ans = 0
for i in range(n//r+1):
    for j in range(n//g+1):
        if r*i + g*j > n:
            break
        if (n - r*i - g*j) == 0 or ((n - r*i - g*j) >= b and (n - r*i - g*j) % b == 0):
            ans += 1
print(ans)

### FIXED CODE ###

r, g, b, n = map(int, input().split())

ans = 0
for i in range(n//r+1):
    for j in range(n//g+1):
        if r*i + g*j > n:
            break
        if (n - r*i - g*j) == 0 or ((n - r*i - g*j) >= b and (n - r*i - g*j) % b == 0):
            ans += 1
print(ans)
### BUGGY CODE ###

# 2020/02/09
# Educational DP Contest / DP まとめコンテスト - B

# Input
n, k = map(int,input().split())
h = list(map(int,input().split()))

dp = [0] * n

for i in range(1, n):
    j = max(0, i-k)
    minh = 10 ** 10
    while(j < i):
        acost = abs(h[i] - h[j]) + dp[j]
        if minh > acost:
            minh = acost
        j = j + 1
    dp[i] = minh

# Output
print(dp[n-1])

### FIXED CODE ###

# 2020/02/09
# Educational DP Contest / DP まとめコンテスト - B

# Input
n, k = map(int,input().split())
h = list(map(int,input().split()))

dp = [10 ** 10] * n
dp[0] = 0

for i in range(1, n):
    j = max(0, i-k)
    while(j < i):
        dp[i] = min(dp[i], abs(h[i] - h[j]) + dp[j])
        j = j + 1

# Output
print(dp[n-1])
### BUGGY CODE ###

import bisect
n = int(input())
al = [int(a) for a in input().split()]
bl = [int(b) for b in input().split()]
cl = [int(c) for c in input().split()]

al.sort()
bl.sort()
cl.sort()

k = 0
for a in al:
    for b in bl[bisect.bisect_right(bl, a):]:
        k += n - bisect.bisect_right(cl, b)
print(k)

### FIXED CODE ###

import bisect
n = int(input())
al = [int(a) for a in input().split()]
bl = [int(b) for b in input().split()]
cl = [int(c) for c in input().split()]

al.sort()
bl.sort()
cl.sort()

k = 0
for b in bl:
    k += bisect.bisect_left(al, b) * (n - bisect.bisect_right(cl, b))
print(k)
### BUGGY CODE ###

import re

N, Q = [int(i) for i in input().split()]
S = input()
ans = []
for i in range(Q):
    l, r = [int(i) for i in input().split()]
    l -= 1
    s = S[l:r]
    ret = re.findall(r"AC", s)
    ans.append(ret)
for a in ans:
    print(len(a))


### FIXED CODE ###

N, Q = [int(i) for i in input().split()]
S = input()
t = [0] * (N + 1)
for i in range(N):
    end = i + 2
    t[i + 1] = t[i] + (1 if S[i:end] == "AC" else 0)
for i in range(Q):
    l, r = [int(i) for i in input().split()]
    print(t[r - 1] - t[l - 1])
### BUGGY CODE ###

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


ans=10**100
for i in range(n):
    a=s.count('W',0,i)
    b=s.count('E',i+1,n)
    if a+b<=ans:
        ans=a+b
print(ans)


### FIXED CODE ###

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

l=[]
c=s.count('E',1)
for i in range(1,n):
    if s[i-1]=='W':
        c+=1
    if s[i]=='E':
        c-=1
    l.append(c)
print(min(min(l),s.count('E')))
### BUGGY CODE ###

def gcdf(a):
    a.sort()
#    print("a2:",a)
    a0=a[0]
    a=[int(x%a0) for x in a if x%a0 != 0]
#    print("a2:",a)
    if len(a)==0:
        return a0
    else:
        a.append(a0)
        a0=min(a)
        return gcdf(a) 

#n=8
#a=[746130, 1385670, 4849845, 881790, 3233230, 1939938, 570570, 510510]
#ans=[19]
#n=2
#a=[1000000000, 1000000000]
#n=5
#a=[15, 18, 24, 36, 81]
#n=3
#a=[7, 6, 8]
n=int(input())
a=[]
for i in map(int,input().split()):
    a.append(i)
if n==2:
    print(max(a))
elif n<2**10:
    gcdv=0
    for i in range(n):
        acpy=list(a)
        del acpy[i]
        gcdx=gcdf(acpy)
        if gcdx>gcdv:
            gcdv=gcdx
    print(gcdv)
else:
    m=int(n**(1/2))
    ns=int(n/m)
    rgcd=[]
    for mi in range(m):
        ms=ns*mi
        if mi==m-1:
            am=a[ms:n]
        else:
            am=a[ms:ms+ns]
        gcdm=gcdf(am)
        rgcd.append(gcdm)
    gcdv=0

    for mi in range(m):
        rgcd1=list(rgcd)
        del rgcd1[mi]
        gcdrg1=gcdf(rgcd1)
        ms=ns*mi
        if mi==m-1:
            am=a[ms:n]
        else:
            am=a[ms:ms+ns]
#        print(mi,gcdf(am),len(am),gcdf(rgcd1))
        for i in range(len(am)):
            acpy=list(am)
#            del acpy[i]
#            acpy.append(gcdrg1)
            acpy[i]=gcdrg1
            gcdx=gcdf(acpy)
            if gcdx>gcdv:
                gcdv=gcdx
    print(gcdv)


### FIXED CODE ###

def gcdf(a):
    a.sort()
#    print("a2:",a)
    a0=a[0]
    a=[int(x%a0) for x in a if x%a0 != 0]
#    print("a2:",a)
    if len(a)==0:
        return a0
    else:
        a.append(a0)
        a0=min(a)
        return gcdf(a) 

#n=8
#a=[746130, 1385670, 4849845, 881790, 3233230, 1939938, 570570, 510510]
#ans=[19]
#n=2
#a=[1000000000, 1000000000]
#n=5
#a=[15, 18, 24, 36, 81]
#n=3
#a=[7, 6, 8]
n=int(input())
a=[]
for i in map(int,input().split()):
    a.append(i)
if n==2:
    print(max(a))
elif n<2**10:
    gcdv=0
    for i in range(n):
        acpy=list(a)
        del acpy[i]
        gcdx=gcdf(acpy)
        if gcdx>gcdv:
            gcdv=gcdx
    print(gcdv)
else:
    m=int(n**(1/2))
    ns=int(n/m)
    rgcd=[]
    for mi in range(m):
        ms=ns*mi
        if mi==m-1:
            am=a[ms:n]
        else:
            am=a[ms:ms+ns]
        gcdm=gcdf(am)
        rgcd.append(gcdm)
    gcdv=0

    for mi in range(m):
        rgcd1=list(rgcd)
        del rgcd1[mi]
        gcdrg1=gcdf(rgcd1)
        ms=ns*mi
        if mi==m-1:
            am=a[ms:n]
        else:
            am=a[ms:ms+ns]
#        print(mi,gcdf(am),len(am),gcdf(rgcd1))
        for i in range(len(am)):
            acpy=list(am)
#            del acpy[i]
#            acpy.append(gcdrg1)
            acpy[i]=gcdrg1
            gcdx=gcdf(acpy)
            if gcdx>gcdv:
                gcdv=gcdx
    print(gcdv)
### BUGGY CODE ###

N, M = map(int, input().split())
H = list(map(int, input().split()))
A = []
B = []
for _ in range(M):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
ans = 0
for i in range(N):
    flag = 0
    for j in range(M):
        if A[j] == i+1:
            if H[B[j]-1] >= H[i]:
                flag = 1
        if B[j] == i+1:
            if H[A[j]-1] >= H[i]:
                flag = 1
    if flag == 0:
        ans += 1
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
H = list(map(int, input().split()))
count = [0]*N
ans = 0
for _ in range(M):
    a, b = map(int, input().split())
    if H[a-1] > count[b-1]:
        count[b-1] = H[a-1]
    if H[b-1] > count[a-1]:
        count[a-1] = H[b-1]
for i in range(N):
    if H[i] > count[i]:
        ans += 1
print(ans)
### BUGGY CODE ###

n = input()

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

total = 1

if str(a) in '0':
	total = 0
else:
	for i in a:
		total *= i

if total > 10**18:
	total = -1

print(total)


### FIXED CODE ###

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

total = 1
li.sort()
for a in li:
    if a == 0:
        total = 0
        break
    total *= a
    if 10 ** 18 < total:
        total = -1
        break
print(total)
### BUGGY CODE ###

a,b,x=map(int,input().split())
count=0
for i in range(a,b+1):
    if i%x==0:
        count+=1
print(count)


### FIXED CODE ###

a,b,x=map(int,input().split())
print(b//x-(a-1)//x)
### BUGGY CODE ###

n= int(input())
a_list = list(map(int, input().split()))
 
ans=1
for i in range(n):
  ans=ans*a_list[i]
  if ans==0:
    break
  
if ans>1000000000000000000:
  ans=-1
  
print(ans)

### FIXED CODE ###

n= int(input())
a_list = list(map(int, input().split()))
 
a_list = [n for n in a_list if n!=1]  
#print(a_list)
ans=1

if 0 in a_list:
  ans=0
elif len(a_list)>56:
  ans=-1
else:
  for i in a_list:
    ans=ans*i
  if ans>1000000000000000000:
      ans=-1
  
print(ans)
### BUGGY CODE ###

import copy
n=int(input())
l=[int(input()) for x in range(n)]
ans=[]
for i in range(n):
    ans=copy.copy(l)
    ans.remove(l[i])
    print(max(ans))
    ans.clear

### FIXED CODE ###

import copy
n = int(input())
l=[int(input()) for x in range(n)]
ll=copy.copy(l)
ll.sort()
setl=list(set(l))
setl.sort()
m=max(l)

for i in range(n):
    if len(setl)==1:
        print(m)
    else:
        second=ll[-2]
        if l[i]==m:
            print(second)
        else:
            print(m)
### BUGGY CODE ###

N,M,Q=map(int,input().split())
Town=[[int(i) for i in input().split()] for i in range(M)]
Town.sort(key=lambda x:x[0])

def BS_left(x,L,s):
  L_copy=L[:]
  left=0
  if L[s-1]<x:
    return s-1
  else:
    while s>2:
      if L_copy[s//2]<x:
        L_copy=L_copy[s//2:s]
        left+=s//2
        s=s-s//2
      else:
        L_copy=L_copy[0:s//2+1]
        s=s//2+1
    if L[left]>=x:
      return left-1
    else:
      return left

def BS_right(x,L,s):
  L_copy=L[:]
  right=s-1
  if L[0]>x:
    return 0
  else:
    while s>2:
      if L_copy[s//2]<=x:
        L_copy=L_copy[s//2:s]
        s=s-s//2
      else:
        L_copy=L_copy[0:s//2+1]
        right+=-s//2+1
        s=s//2+1
    if L[right]<=x:
      return right+1
    else:
      return right

ans=[0]*Q
for i in range(Q):
  p,q=map(int,input().split())
  for i in zip(*Town):
    TownL=i
    break
  a=BS_left(p,TownL,M)+1
  newTown=Town[a:]
  if M-a==0:
    print(0)
  else:
    newTown.sort(key=lambda x:x[1])
    e=0
    for i in zip(*newTown):
      if e==0:
        e+=1
      else:
        TownR=i
        break
    b=BS_right(q,TownR,M-a)
    if b==1 and TownR[0]>q:
      print(0)
    else:
      print(b)


### FIXED CODE ###

N,M,Q=map(int,input().split())
Train=[[int(i) for i in input().split()] for i in range(M)]
Map=[[0]*(N+1) for i in range(N+1)]
for i in Train:
  x,y=i[0],i[1]
  Map[y][x]+=1
for a in range(1,N+1):
  for b in range(1,N+1):
    if b<=N-1:
      Map[a][b+1]=Map[a][b]+Map[a][b+1]
    if a>=2:
      Map[a][b]=Map[a-1][b]+Map[a][b]
for i in range(Q):
  p,q=map(int,input().split())
  print(Map[q][q]-Map[q][p-1]-Map[p-1][q]+Map[p-1][p-1])
### BUGGY CODE ###

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

end_list = list(filter(lambda x: x[1] == N, ab_list))

res = False

for end in end_list:
    if len(list(filter(lambda x: (x[1] == end[0]) and (x[0] == 1) or end[0] == 1, ab_list))) > 0:
        res = True
        break


if res:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")


### FIXED CODE ###

N, M = map(int, input().split())
ab_list = [list(map(lambda x: int(x) - 1, input().split())) for i in range(M)]

lis = [[] for i in range(N)]

for i in range(M):
    lis[ab_list[i][0]].append(ab_list[i][1])

que = [[0, 0, lis[0], []]]
ends = []
res = False

while que:
    count, now, next_nodes, visited = que.pop()
    visited.append(now)
    if now == N - 1:
        ends = visited[:]
    for node in next_nodes:
        if node in visited or count == 2:
            continue
        que.append([count + 1, node, lis[node], visited[:]])

if N - 1 in ends:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

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

cnt = 0
for org in range(N-1):
    for i in range(org+A[org],N):
        if A[org]+A[i]==i-org:
            cnt+=1
print(cnt)

### FIXED CODE ###

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

L = {}
R_val = []
for i in range(N):
    if i+A[i] not in L:
        L[i+A[i]] = 0
    L[i+A[i]]+=1
    R_val.append(i-A[i])
    
ans = 0
for one in R_val:
    if one in L:
        ans+=L[one]
print(ans)
### BUGGY CODE ###

def per(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r=n-r
    return g1[n] * g2[r] % mod

mod = 10**9+7 #出力の制限
N = 10**5+5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


n=int(input())
A=[1]
for i in range(1,n-1):
  A.append(A[-1]*(i+1)+per(i,i,mod))
X=list(map(int,input().split()))
Y=[X[1]-X[0]]
for i in range(2,n):
  Y.append(X[i]-X[i-1])
ans=0
for i in range(n-1):
  if n-2-i==0:
    ans=ans+A[i]*Y[i]
  else:
    ans=(ans+A[i]*per(n-1,n-2-i,mod)*Y[i])%(10**9+7)
print(ans%mod)

### FIXED CODE ###

n=int(input())
x=list(map(int,input().split()))
a=1
B=[1,1]
mod=10**9+7
for i in range(2,n):
  a=a*i%mod
  B.append(pow(i,mod-2,mod))
d=[0]*(n-1)
for i in range(n-1):
  d[i]=x[i+1]-x[i]
D=[d[-1]]
for i in range(n-2):
  D.append(D[-1]+d[-2-i])
D=D[::-1]
ans=0
for i in range(n-1):
  ans=(ans+D[i]*a*B[i+1])%mod
print(ans)
### BUGGY CODE ###

K, S = map(int, input().split())
X = range(K + 1)
Y = range(K + 1)
Z = range(K + 1)
count = 0
for i in X:
    for p in Y:
        for o in Z:
            if (S - (i + p)) > K:
                break
            if (i + p + o) == S:
                count += 1
            elif (i + p + o) > S:
                break
print(count)

### FIXED CODE ###

K, S = map(int, input().split())
X = range(K + 1)
Y = range(K + 1)
Z = range(K + 1)

count = 0

for i in X:
    for p in Y:
        if (S - (i + p)) in Z:
            count += 1

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

N,M=map(int, input().split())
L=[ [] for _ in range(N)]
Y=[]
X=[]
for _ in range(M):
    a,b = input().split()
    a=int(a)
    b=int(b)
    L[a-1].append(b)
    X.append({a:b})
for _ in range(N) :
    Y.append(sorted(L[_]))
for i in range(M) :
    for k,v in X[i].items():
        z='%06d' % (Y[k-1].index(v)+1)
        Z='%06d' % k
        print(Z+z)


### FIXED CODE ###

N,M = map(int,input().split())
L = []
for i in range(M):
    l = list(map(int,input().split()))+[i]
    L.append(l)
cnt = 0
tmp = []
M = sorted(L,key = lambda x: (x[0],x[1]))
for x in M:
    if tmp == x[0]:
        x.append(cnt+1)
        cnt += 1
    else:
        tmp = x[0]
        cnt = 0
        x.append(cnt)
M = sorted(L,key = lambda x:x[2])
#print(M)
for x in M:
    st = str(x[0]).zfill(6)
    st += str(x[3]+1).zfill(6)
    print(st)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

def map_int_input():
    return map(int, input())

MII = map_int_input

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

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

def LII_split():
    return list(map(int, input().split()))

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

N = input_int()
S = input()

if N < 3:
    print(0)
    exit()
count = 0
rs = []
gs = []
bs = []
for i in range(len(S)):
    if S[i] == 'R':
        rs.append(i)
    elif S[i] == 'G':
        gs.append(i)
    else:
        bs.append(i)
count = 0
for r in rs:
    for g in gs:
        for b in bs:
            rgb = [r, g, b]
            rgb.sort()
            if rgb[1]-rgb[0] != rgb[2]-rgb[1]:
                count += 1



# for i in range(N - 2):
#     for j in range(i + 1, N - 1):
#         if S[i] == S[j]:
#             continue
#
#         for k in range(j + 1, N):
#             if S[j] == S[k] or S[i] == S[k] or j - i == k - j:
#                 continue
#             else:
#                 count += 1
print(count)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

def map_int_input():
    return map(int, input())

MII = map_int_input

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

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

def LII_split():
    return list(map(int, input().split()))

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

N = input_int()
S = input()

if N < 3:
    print(0)
    exit()
rs = []
gs = []
bs = []
for i in range(len(S)):
    if S[i] == 'R':
        rs.append(i)
    elif S[i] == 'G':
        gs.append(i)
    else:
        bs.append(i)
count = len(rs) * len(gs) * len(bs)
# for r in rs:
#     for g in gs:
#         for b in bs:
#             rgb = [r, g, b]
#             rgb.sort()
#             if rgb[1]-rgb[0] != rgb[2]-rgb[1]:
#                 count += 1

for skip in range(1, N // 2 + 1):
    for i in range(N - 2):
        if i + 2 * skip > N - 1:
            break
        elif S[i] == S[i + skip] or S[i + skip] == S[i + 2 * skip] or S[i] == S[i + 2 * skip]:
            continue
        else:
            count -= 1

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

N, M = map(int, input().split())
cnt = 0
li = []

for i in range(N):
    li.append(M)

# print(li)

for i in range(M):
    L, R = map(int, input().split())
    for j in range(L-1, R):
        li[j] = li[j] - 1
        # print(li)

for i in range(0, len(li)):
    if li[i] == 0:
        cnt += 1

print(cnt)

### FIXED CODE ###

N, M = map(int, input().split())

L = []

for i in range(M):
    LR = list(map(int, input().split()))
    L.append(LR)

res = [L[0][0], L[0][1]]

for i in range(M):
    res = [max(res[0], L[i][0]), min(res[1], L[i][1])]

if res[1] < res[0]:
    print(0)
else: 
    print(res[1] - res[0] + 1)
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()
ans = [0]*Q
for i in range(Q):
    l,r = map(int,input().split())
    print(S[l-1:r].count("AC"))


### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
t = [0]*(N+1)
l = [0]*Q
r = [0]*Q
for i in range(N-1):
	t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
    l,r = map(int,input().split())
    print(t[r-1]-t[l-1])
### BUGGY CODE ###

import sys
from collections import Counter

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

#１回のクエリで半分に空席がある場所を絞る
end = ri()
print(0)
S = rs()
if S == 'Vacant':
    exit()
start = 0
cur = S   
while end > start + 2:
    target = start + max(2, (end - start) // 4 * 2)
    print(target)
    S = rs()
    if S == 'Vacant':
        exit()
    if cur != S:
        end = target
    else:
        start = target
print(start + 1)
#24


### FIXED CODE ###

N = int(input())

def ask(n):
    print(n, flush=True)
    resp = input().rstrip()[0]
    if resp == 'V':
        exit()
    return resp

def condition(L,R,resp_L,resp_R):
    if (R-L)&1:
        return resp_L == resp_R
    else:
        return resp_L != resp_R

resp = ask(0)

L = 0
R = N
resp_L = resp
resp_R = resp
for _ in range(19):
    M = (L + R) // 2
    resp_M = ask(M)
    if condition(L,M,resp_L,resp_M):
        R,resp_R = M,resp_M
    else:
        L,resp_L = M,resp_M
### BUGGY CODE ###

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

B=[(j,i) for i,j in enumerate(A)]
B.sort(reverse=True)

dp=[[0]*(N+1) for _ in range(N+1)]

c=0
for v,k in B:
    for i in range(c+1):
        dp[i+1][c-i]=max(dp[i+1][c-i],dp[i][c-i]+abs(v*(k-i)))
        dp[i][c-i+1]=max(dp[i][c-i+1],dp[i][c-i]+abs(v*(N-(c-i)-k-1)))
    c+=1

ans=0
for i in range(N):
    ans=max(ans,dp[i][N-i])

print(ans)

### FIXED CODE ###

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

d={}

for i,j in enumerate(A):
    d[i]=j

d=sorted(d.items(),key=lambda x:x[1],reverse=True)

dp=[[0]*(N+1) for _ in range(N+1)]

c=0
for k,v in d:
    for i in range(c+1):
        dp[i+1][c-i]=max(dp[i+1][c-i],dp[i][c-i]+abs(v*(k-i)))
        dp[i][c-i+1]=max(dp[i][c-i+1],dp[i][c-i]+abs(v*(N-(c-i)-k-1)))
    c+=1

ans=0
for i in range(N):
    ans=max(ans,dp[i][N-i])

print(ans)