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

import sys
read=sys.stdin.buffer.readline

class BIT:
    def __init__(self,N):
        self.N=N
        self.bit=[0]*N
    def add(self,a,w):
        x=a
        while(x<self.N):
            self.bit[x]+=w
            x|=x+1
    def get(self,a):
        ret,x=0,a-1
        while(x>=0):
            ret+=self.bit[x]
            x=(x&(x+1))-1
        return ret
    def cum(self,l,r):
        return self.get(r)-self.get(l)

def main():
    def update(x,i):
        if good[x]==-1:
            good[x]=i
            bit.add(i,1)
        else:
            bit.add(good[x],-1)
            good[x]=i
            bit.add(good[x],1)
        return
    
    N,Q=map(int,read().split())
    c=list(map(int,read().split()))
    li=[list(map(lambda x:int(x)-1,read().split())) for i in range(Q)]
    Query=[(li[i][0],li[i][1],i) for i in range(Q)]
    Query.sort(key=lambda x:x[1])
    ans=[-1]*Q
    good=[-1]*(N+1)
    bit=BIT(N)

    i=0
    for L,R,w in Query:
        while(i<=R):
            update(c[i],i)
            i+=1
        ans[w]=bit.cum(L,R+1)

    print(*ans,sep='\n')
    return
    
if __name__=='__main__':
    main()


### FIXED CODE ###

import sys
read=sys.stdin.buffer.readline

class BIT:
    def __init__(self,N):
        self.N=N
        self.bit=[0]*N
    def add(self,a,w):
        x=a
        while(x<self.N):
            self.bit[x]+=w
            x|=x+1
    def get(self,a):
        ret,x=0,a-1
        while(x>=0):
            ret+=self.bit[x]
            x=(x&(x+1))-1
        return ret
    def cum(self,l,r):
        return self.get(r)-self.get(l)

def main():
    def update(x,i):
        if good[x]==-1:
            good[x]=i
            bit.add(i,1)
        else:
            bit.add(good[x],-1)
            good[x]=i
            bit.add(good[x],1)
        return
    
    N,Q=map(int,read().split())
    c=tuple(map(int,read().split()))
    Query=[]
    for i in range(Q):
        l,r=map(lambda x:int(x)-1,read().split())
        Query.append((l,r,i))
    Query.sort(key=lambda x:x[1])
    ans=[-1]*Q
    good=[-1]*(N+1)
    bit=BIT(N)

    i=0
    for L,R,w in Query:
        while(i<=R):
            update(c[i],i)
            i+=1
        ans[w]=bit.cum(L,R+1)

    print(*ans,sep='\n')
    return
    
if __name__=='__main__':
    main()
### BUGGY CODE ###

def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    INF = 10**9

    H, W, K = map(int, input().split())
    chocolate = [ list(map(int, list(input()[:-1]))) for _ in range(H) ]
    
    loop_H = range(H)
    loop_W = range(W)
    min_cut = INF-1
    for div in range(1 << (H-1)):
        # 横割りでグループ分け
        group = [[]]
        group_number = 0
        for i in loop_H:
            group[group_number].append(i)
            if div >> i & 1:
                group.append([])
                group_number += 1
        # グループごと白チョコを数える
        white_chocolate = [ [0]*(W+1) for _ in range(group_number+1) ]
        for i in loop_W:
            for g in range(group_number+1):
                for j in group[g]:
                    white_chocolate[g][i] += chocolate[j][i]
        # 縦に切っていく
        cut = group_number
        zeros = [0] * len(white_chocolate)
        now = zeros.copy()
        for w in loop_W:
            for g in range(len(white_chocolate)):
                if white_chocolate[g][w] > K:
                    cut = INF
                    break
                else:
                    now[g] += white_chocolate[g][w]
                if now[g] + white_chocolate[g][w+1] > K:
                    cut += 1
                    now = zeros.copy()
                    break
            if cut == INF:
                break
        if cut < min_cut:
            min_cut = cut
    print(min_cut)

main()

### FIXED CODE ###

def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    INF = 10**9

    H, W, K = map(int, input().split())
    chocolate = [ input()[:-1] for _ in range(H) ]
    
    loop_H = range(H)
    loop_W = range(W)
    min_cut = INF-1
    for div in range(1 << (H-1)):
        # 横割りでグループ分け
        group = [[]]
        group_number = 0
        for i in loop_H:
            group[group_number].append(i)
            if div >> i & 1:
                group.append([])
                group_number += 1
        # 縦に切っていく
        cut = group_number
        zeros = [0] * len(group)
        cnt = zeros.copy()
        w = 0
        while w < W:
            now = zeros.copy()
            for g in range(len(group)):
                for i in group[g]:
                    if chocolate[i][w] == '1':
                        now[g] += 1
                if now[g] > K:
                    cut = INF
                    break
                if cnt[g] + now[g] > K:
                    cut += 1
                    w -= 1
                    cnt = zeros.copy()
                    break
                cnt[g] += now[g]
            w += 1
        if cut < min_cut:
            min_cut = cut
    print(min_cut)

main()
### BUGGY CODE ###

n = int(input())

cand = []
for i in range(1, n):
  if n % i == 0:
    cand.append((i - 1) + (n // i - 1))
print(min(cand))
    

### FIXED CODE ###

import math

n = int(input())

cand = []
for i in range(1, int(math.sqrt(n))+1):
  if n % i == 0:
    cand.append((i - 1) + (n // i - 1))
print(min(cand))
### BUGGY CODE ###

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

ret = 0
mod = int(1e9) + 7

cum = [0] * (n + 1)

for i in range(n):
    cum[i + 1] = cum[i] + a[i]


def inv(x):
    return pow(x, mod - 2, mod)


for i in range(n):
    for j in range(n):
        if i == j:
            continue
        ret += inv(abs(j - i)+1) * (a[j])
        ret %= mod
ret += cum[-1]
ret %= mod
for i in range(2, n + 1):
    ret *= i
    ret %= mod
print(ret)


### FIXED CODE ###

mod = int(1e9 + 7)


def inv(x):
    return pow(x, mod - 2, mod)

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

memo = [inv(i + 1) for i in range(100000)]
for i in range(1, 100000):
    memo[i] = (memo[i] + memo[i - 1]) % mod

p = 1
for i in range(1, n + 1):
    p = p * i % mod
ret = 0
for i in range(n):
    ret = (ret +a[i] * (memo[i] + memo[n - i- 1] - 1) % mod * p) % mod

print(ret % mod)
### BUGGY CODE ###

N, X = map(int, input().split())
S = sorted([int(a) for a in input().split()])[::-1]
P = 10**9+7
fact = [1]
for i in range(N+10):
    fact.append(fact[-1]*(i+1)%P)

def calc(k, x):
    if k >= N:
        return x
    if x == S[-1]:
        return 0
    if x < S[-1]:
        return (x*fact[N-k]) % P
    return (calc(k+1, x%S[k]) + calc(k+1, x) * (N-k-1)) % P

print(calc(0, X))


### FIXED CODE ###

from functools import lru_cache
N, X = map(int, input().split())
S = sorted([int(a) for a in input().split()])[::-1]
P = 10**9+7
fact = [1]
for i in range(N+10):
    fact.append(fact[-1]*(i+1)%P)

@lru_cache(None)
def calc(k, x):
    if k >= N:
        return x
    if x < S[-1]:
        return (x*fact[N-k]) % P
    return (calc(k+1, x%S[k]) + calc(k+1, x) * (N-k-1)) % P

print(calc(0, X))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
B = [1] * (max(A) + 1)
for a in A:
    for k in range(a  * 2,len(B),a):
            B[k] = 0
print(sum(B[a] == 1 and A.count(a) == 1 for a in A))


### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
counter = Counter(A)
B = [1] * (max(A) + 1)
for a in A:
    for k in range(a  * 2,len(B),a):
            B[k] = 0
print(sum(B[a] == 1 and counter[a] == 1 for a in A))
### BUGGY CODE ###

input()
S = [int(i) for i in input()]
cnt = 0
for i in range(0, 1000):
  c = (i//100, (i//10)%10, i%10)
  f = 0
  for s in S:
    if s == c[f]:
      f += 1 
      if f==3:break 
  if f==3:cnt += 1
print(cnt)


### FIXED CODE ###

input()
S = [int(i) for i in input()]
cnt = 0
for i in range(0, 1000):
  c = (i//100, (i//10)%10, i%10)
  f = 0
  for s in S:
    if s == c[f]:
      f += 1 
      if f==3:break 
  if f==3:cnt += 1
print(cnt)
### BUGGY CODE ###

n,q = list(map(int, input().split()))
s = input()
s_ps=[]
for i in range(n-1):
    if s[i:i+2]=='AC':
        s_ps.append(i)

for _ in range(q):
    l,r=list(map(int, input().split()))
    count =0
    for i in s_ps:
        if l-1<=i and i < r-1:
            count +=1
    print(count)

### FIXED CODE ###


n,q = list(map(int, input().split()))
s = input()
ans = [0]*(n+1)
lr=[list(map(int, input().split())) for _ in range(q)]
for i in range(1,n):
    
    if s[i-1]=='A' and s[i]=='C':
        ans[i+1] = ans[i] + 1
    else:
        ans[i+1]= ans[i]
#print(ans)
for i in range(q):
    print(ans[lr[i][1]]-ans[lr[i][0]])
### BUGGY CODE ###

n, k, q = map(int, input().split())
p = [k]*n
a = []
ans = ['No'] * n

for i in range(q):
    a.append(int(input()))

for i in range(len(a)):
    idx = a[i] - 1
    for j in range(len(p)):
        if j != idx:
            p[j] = p[j] - 1


for i in range(len(p)):
    if p[i] > 0:
        ans[i] = 'Yes'

# print(p)
# print(a)
# print(ans)

for i in range(len(ans)):
    print(ans[i])

### FIXED CODE ###

n, k, q = map(int, input().split())
p = [k]*n
a = []
ans = ['No'] * n
counts = {}

for i in range(q):
    a.append(int(input()))

for i in range(len(a)):
    key = a[i]
    if key in counts:
        counts[key] += 1
    else:
        counts[key] = 1

for key, value in counts.items():
    idx = key - 1
    p[idx] += value

#print('p: ' + str(p))
for i in range(len(p)):
    p[i] -= q

for i in range(len(p)):
    if p[i] > 0:
        ans[i] = 'Yes'

# print('counts: ' + str(counts))
# print('p: ' + str(p))
# print(a)
# print(ans)

for i in range(len(ans)):
    print(ans[i])
### BUGGY CODE ###

#bit全探索する
INF = 5000

def dp(n, medichine, Ma, Mb):
    INF =  5000
    if n == 0: #終端
        List = [[0, 0, 0], medichine[0]]
        if medichine[n][0] * Mb == medichine[n][1] * Ma:
            cost = medichine[0][2]
        else:
            cost = INF
    else: #n-1をもとにnについて計算
        previous = dp(n-1, medichine, Ma, Mb)
        List = previous[0][:]
        cost = previous[1]
        for x in previous[0]:
            A = x[0] + medichine[n][0]
            B = x[1] + medichine[n][1]
            C = x[2] + medichine[n][2]
            if C < cost:
                List.append([A, B, C])
                if A * Mb == B * Ma:
                    cost = C
    return List, cost



N, Ma, Mb = map(int, input().split())
medichine = {}
for i in range(N):
    Lst = [int(x) for x in input().split()]
    medichine[i] = Lst
ans = dp(N-1, medichine, Ma, Mb)
cost = ans[1]
if cost != INF:
    print(cost)
else:
    print(-1)

### FIXED CODE ###

import collections
import copy
INF = 10000

#入力
N, Ma, Mb = map(int, input().split())
medichine = [tuple(map(int, input().split())) for _ in range(N)]

dp = {}
#dp初期化
dp = collections.defaultdict(lambda:INF)
dp[0,0] = 0

for a, b, c in medichine:
    dp_ = copy.copy(dp)
    for ca,cb in dp.keys():
        dp_[ca+a, cb+b] = min(dp_[ca+a, cb+b], dp[ca,cb]+c)
    dp = dp_    

ans = INF
for ca,cb in dp.keys():
    if ca == cb == 0: continue
    if ca*Mb == cb*Ma:
        ans = min(ans, dp[ca,cb])
        
print(-1 if ans == INF else ans)
### BUGGY CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

H,W,A,B=inpl()
ans = 0

def Comb(n,k):#nCk
	gyakugen = [1]*(n+1)
	fac = [1]*(n+1)

	for i in range(1,n+1):
		fac[i] = (fac[i-1]*i)%mod
	gyakugen[n] = pow(fac[n],mod-2,mod)

	for i in range(n,0,-1):
		gyakugen[i-1] = (gyakugen[i]*i)%mod
	com = [1]*(n+1)

	for i in range(1,n+1):
		com[i] = (fac[n]*gyakugen[i]*gyakugen[n-i])%mod

	return com[k]%mod

for x1 in range(B+1,W+1):
	y1 = H-A
	x2 = A
	y2 = W-x1+1
	ans += (Comb(x1+y1-2,y1-1)*Comb(x2+y2-2,y2-1))%mod
	ans %= mod

print(ans)


### FIXED CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

H,W,A,B=inpl()
ans = 0

MAX = H+W
fac = [1]*(MAX+1)
for i in range(1,MAX+1):
	fac[i] = (fac[i-1]*i)%mod

gyakugen = [1]*(MAX+1)
gyakugen[MAX] = pow(fac[MAX],mod-2,mod)
for i in range(MAX,0,-1):
	gyakugen[i-1] = (gyakugen[i]*i)%mod

def Comb(n,k):#nCk
	return (fac[n]*gyakugen[k]*gyakugen[n-k])%mod

for x1 in range(B+1,W+1):
	y1 = H-A
	x2 = A
	y2 = W-x1+1
	ans += (Comb(x1+y1-2,y1-1)*Comb(x2+y2-2,y2-1))%mod
	ans %= mod

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

class UnionFind:
    def __init__(self, elements):
        self.elements = {e: -1 for e in elements}

    def same(self, a, b):
        return self.find(a) == self.find(b)

    def find(self, a):
        parent = self.elements[a]
        if parent < 0:
            return a
        self.elements[a] = self.find(parent)
        return self.elements[a]

    def unite(self, a, b):
        a_parent = self.find(a)
        b_parent = self.find(b)

        # already same union
        if a_parent == b_parent:
            return

        self.elements[a_parent] += self.elements[b_parent]
        self.elements[b_parent] = a_parent


N, K, L = map(int, input().split())
roads = []
trains = []
for _ in range(K):
    roads.append(list(map(int, input().split())))
for _ in range(L):
    trains.append(list(map(int, input().split())))

road_union = UnionFind(i for i in range(1, N + 1))
for road in roads:
    road_union.unite(road[0], road[1])

train_union = UnionFind(i for i in range(1, N + 1))
for train in trains:
    train_union.unite(train[0], train[1])

ma = dict()
for i in range(N):
    p = (road_union.find(i + 1), train_union.find(i + 1))
    ma.setdefault(p, 0)
    ma[p] += 1

for i in range(N):
    p = (road_union.find(i + 1), train_union.find(i + 1))
    print(ma[p], end=' ')


### FIXED CODE ###

class UnionFind:
    def __init__(self, elements):
        self.elements = {e: -1 for e in elements}

    def same(self, a, b):
        return self.find(a) == self.find(b)

    def find(self, a):
        parent = self.elements[a]
        if parent < 0:
            return a
        self.elements[a] = self.find(parent)
        return self.elements[a]

    def unite(self, a, b):
        a_parent = self.find(a)
        b_parent = self.find(b)

        # already same union
        if a_parent == b_parent:
            return

        self.elements[a_parent] += self.elements[b_parent]
        self.elements[b_parent] = a_parent


N, K, L = map(int, input().split())
road_union = UnionFind(i for i in range(1, N + 1))
for _ in range(K):
    a, b = map(int, input().split())
    road_union.unite(a, b)

train_union = UnionFind(i for i in range(1, N + 1))
for _ in range(L):
    a, b = map(int, input().split())
    train_union.unite(a, b)

ma = dict()
for i in range(N):
    p = (road_union.find(i + 1), train_union.find(i + 1))
    ma[p] = ma.get(p, 0) + 1

for i in range(N):
    p = (road_union.find(i + 1), train_union.find(i + 1))
    print(ma[p], end=' ')
### 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:
        if a[buf-1]==2:
            print(len(b))
            break
        elif a[buf-1] in b:
            print(-1)
            break
        b.append(a[buf-1])
        buf=a[buf-1]

### 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 ###

n,t = map(int,input().split())
now = [0 for _ in range(t+1)]
wv = []
for _ in range(n):
  wv.append(list(map(int,input().split())))
wv.sort(key=lambda x:x[0])
for i in range(n):
  w,v = wv[i]
  last = now
  now = []
  for f in range(t):
    if f - w >= 0:
      now.append(max(last[f],last[f-w]+v))
    else:
      now.append(last[f])
  now.append(max(last[-2]+v,last[-1]))
  #print(now)
print(now[-1])

### FIXED CODE ###

n,t = map(int,input().split())
now = [0 for _ in range(t+1)]
wv = []
for _ in range(n):
  wv.append(list(map(int,input().split())))
wv.sort(key=lambda x:x[0])
for i in range(n):
  w,v = wv[i]
  last = now
  now = []
  for f in range(t):
    if f - w >= 0:
      now.append(max(last[f],last[f-w]+v))
    else:
      now.append(last[f])
  now.append(max(last[-2]+v,last[-1]))
  #print(now)
print(now[-1])
### BUGGY CODE ###

X = int(input())
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

L = make_divisors(X)
flag = 0
for C in L:
    Y = X//C
    for A in range(Y+1):
        B = A-C
        if A**4 + A**3*B + A**2*B**2 + A*B**3 + B**4 == Y:
            print(A,B)
            flag = 1
        if flag==1:
            break
    if flag==1:
        break

### FIXED CODE ###

X = int(input())
flag = 0
for A in range(-300,301):
    for B in range(-300,301):
        if A**5 - B**5 == X:
            print(A,B)
            flag = 1
        if flag==1:
            break
    if flag==1:
        break
### BUGGY CODE ###

import sys
sys.setrecursionlimit(4100000)

INF = 10 ** 8

H, W = map(int,input().split())
C = list(map(int,input().split()))
D = list(map(int,input().split()))
MAP = []
for _ in range(H):
    MAP.append(list(input()))
d = [[INF for i in range(W)] for j in range(H)]
tx = [1, 0, -1, 0]
ty = [0, 1, 0, -1]
tx_y = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i != 0 or j != 0)]

def dfs(x, y, cnt):
    for i in range(4):
        nx = x + tx[i]
        ny = y + ty[i]
        if 0 <= nx < H and 0 <= ny < W and MAP[nx][ny] == "." and d[nx][ny] > cnt:
            d[nx][ny] = cnt
            dfs(nx, ny, cnt)
    for i, j in tx_y:
        nx = x + i
        ny = y + j
        if 0 <= nx < H and 0 <= ny < W and MAP[nx][ny] == "." and d[nx][ny] > cnt + 1:
            d[nx][ny] = cnt + 1
            dfs(nx, ny, cnt + 1)

d[C[0]-1][C[1]-1] = 0
dfs(C[0]-1, C[1]-1, 0)

if d[D[0]-1][D[1]-1] == INF:
    print(-1)
else:
    print(d[D[0]-1][D[1]-1])

### FIXED CODE ###

from collections import deque
import sys

INF = 10 ** 8

H, W = map(int,input().split())
C = list(map(int,input().split()))
D = list(map(int,input().split()))
MAP = []
for _ in range(H):
    MAP.append(list(input()))
d = [[INF for i in range(W)] for j in range(H)]
tx = [1, 0, -1, 0]
ty = [0, 1, 0, -1]
tx_y = [(i, j) for i in range(-2, 3) for j in range(-2, 3)]

Q = deque()
Q.append([C[0]-1, C[1]-1, 0])

while len(Q) != 0:
    x, y, cnt = Q.popleft()
    
    if x == D[0]-1 and y == D[1]-1:
        print(cnt)
        sys.exit()
    
    for i in range(4):
        nx = x + tx[i]
        ny = y + ty[i]
        if 0 <= nx < H and 0 <= ny < W and MAP[nx][ny] == "." and d[nx][ny] > cnt:
            d[nx][ny] = cnt
            Q.appendleft([nx, ny, cnt])
    
    for i, j in tx_y:
        nx = x + i
        ny = y + j
        if 0 <= nx < H and 0 <= ny < W and MAP[nx][ny] == "." and d[nx][ny] > cnt+1:
            d[nx][ny] = cnt+1
            Q.append([nx, ny, cnt+1])

print(-1)
### BUGGY CODE ###

n, k ,q = list(map(int, input().split()))
li = [input() for i in range(q)]
list = []
for i in range(1,n+1):
    if li.count(str(i)) > q - k:
        list.append('Yes')
    else:
        list.append('No')
[print(x) for x in list]


### FIXED CODE ###

n, k ,q = list(map(int, input().split()))
listAns = [input() for i in range(q)]
score = [0] * n
count = 0
for j in listAns:
    score[int(j) - 1] += 1
for h in score:
    if h > q - k:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
s = 1
x = 0
y = 0
for i in range(n):
    s *= a[i]
    if a[i] == 0:
        y += 1
    if s > 1000000000000000000:
        x += 1

if y != 0:
    print(0)
else:
    if x != 0:
        print(-1)
    else:
        print(s)


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
s = 1
x = 0
y = 0
for i in range(n):
    s *= a[i]
    if a[i] == 0:
        y += 1
    if s > 1000000000000000000:
        s = 0
        x += 1

if y != 0:
    print(0)
else:
    if x != 0:
        print(-1)
    else:
        print(s)
### BUGGY CODE ###

S = input()
reverse = 0
front = []
end = []
n = int(input())
for _ in range(n):
  List = list(input().split())
  #print(List)
  if List[0] == '1':
    reverse += 1
    front,end = end[::-1],front[::-1]
  else:
    if List[1] == '1':
      front.insert(0,List[2])
    else:
      end.append(List[2])
if reverse %2 == 1:
  S = S[::-1]
Answer = ''.join(front) + S + ''.join(end)
print(Answer)

### FIXED CODE ###

S = input()
reverse = 0
front = []
end = []
n = int(input())
for _ in range(n):
  List = list(input().split())
  if List[0] == '1':
    reverse += 1
  else:
    if List[1] == '1':
      if reverse % 2 == 1:
        end.append(List[2])
      else:
        front.append(List[2])
    else:
      if reverse % 2 == 1:
        front.append(List[2])
      else:
        end.append(List[2])
if reverse %2 == 1:
  S = S[::-1]
  front, end = end, front
Answer = ''.join(front[::-1]) + S + ''.join(end)
print(Answer)
### BUGGY CODE ###

a,b,c,d = input().split(' ')
a = int(a)
b = int(b)
c = int(c)
d = int(d)

counter = 0

for i in range(a, b + 1):
    if i % c == 0 or i % d == 0:
        counter += 1

print(b + 1 - a - counter)


### FIXED CODE ###

# 最大公約数
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a


# 最小公倍数
def lcm(a, b):
    return a * b // gcd(a, b)

a,b,c,d = input().split(' ')

a = int(a)
b = int(b)
c = int(c)
d = int(d)

hoge = lcm(c,d)

counter = 0

counter = counter + ((b // c) + (b // d) - (b // hoge))
counter = counter - (((a - 1) // c) + ((a - 1) // d) - ((a - 1) // hoge))

print(b - a + 1 - counter)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

r = [i for i, x in enumerate(s) if x == 'R']
g = [i for i, x in enumerate(s) if x == 'G']
b = [i for i, x in enumerate(s) if x == 'B']
ans = 0

for x in r:
    n = [i for i in g if i>x]
    for y in n:
        m = [i for i in b if i>y]
        for z in m:
            if y-x != z-y:
                ans += 1
    n = [i for i in b if i>x]
    for y in n:
        m = [i for i in g if i>y]
        for z in m:
            if y-x != z-y:
                ans += 1

for x in b:
    n = [i for i in r if i>x]
    for y in n:
        m = [i for i in g if i>y]
        for z in m:
            if y-x != z-y:
                ans += 1
    n = [i for i in g if i>x]
    for y in n:
        m = [i for i in r if i>y]
        for z in m:
            if y-x != z-y:
                ans += 1           
                
for x in g:
    n = [i for i in r if i>x]
    for y in n:
        m = [i for i in b if i>y]
        for z in m:
            if y-x != z-y:
                ans += 1              
    n = [i for i in b if i>x]
    for y in n:
        m = [i for i in r if i>y]
        for z in m:
            if y-x != z-y:
                ans += 1

print(ans)

### FIXED CODE ###

n = int(input())
s = list(input())
r = 0
g = 0
b = 0

for c in s:
    if c == "R":
        r += 1
    if c == "G":
        g += 1
    if c == "B":
        b += 1
ans = r*g*b

for i in range(n):
    for j in range(i+1,n):
        k = 2*j - i
        if k > n-1:
            continue
        x = s[i]
        y = s[j]
        z = s[k]
        if x!= y and y != z and z != x:
            ans -= 1

print(ans)