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

import sys
input=sys.stdin.readline
def create_table(pattern):
    table = [0 for _ in range(len(pattern))]
    j = 0
    for i in range(1, len(pattern)):
        if pattern[i] == pattern[j]:
            j += 1
            table[i] = j
        else:
            table[i] = j
            j = 0
    return table

def kmp_search(string, pattern):
    table = create_table(pattern)
    i = j = 0
    ret=[]
    while i < len(string): #and j < len(pattern):
        if string[i] == pattern[j]:
            i += 1
            j += 1
        elif j == 0:
            i += 1
        else:
            j = table[j]
        if j == len(pattern):
            ret.append(i - j)
            j=table[j-1]
    return ret
#print(kmp_search(list('abcabc'),list('abc')))
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
a.append(a[0])
b.append(b[0])
a2=[]
b2=[]
for i in range(n):
    a2.append(a[i]^a[i+1])
    b2.append(b[i]^b[i+1])
aa=a2+a2
aa.pop(-1)
k=kmp_search(aa,b2)
ans=[]
for i in k:
    if i<n:
      ans.append([i,a[i]^b[0]])
for i in ans:
    print(*i)


### FIXED CODE ###

class KMP:
    def __init__(self, P):
        self.P = P
        self.N = len(P)
        self.T = [0] * (self.N + 1)
        self._compile()

    def _compile(self):
        j = 0
        self.T[0] = -1
        for i in range(1, self.N):
            self.T[i] = j
            j += 1 if self.P[i] == self.P[j] else -j
        self.T[self.N] = j

    def search(self, S):
        NS = len(S)
        i = m = 0
        A = []
        while m + i < NS:
            if self.P[i] == S[m + i]:
                i += 1
                if i != self.N:
                    continue
                A.append(m)
            m += i - self.T[i]
            i = max(0, self.T[i])
        return A

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = [A[i]^A[(i+1)%N] for i in range(N)]
D = [B[i]^B[(i+1)%N] for i in range(N)]
C = C + C[:-1]
K = KMP(D).search(C)
#D string C pattern
for k in K:
    print(k, A[k]^B[0])
### BUGGY CODE ###

import itertools
import heapq
import sys
input = sys.stdin.readline
n,k = map(int,input().split())
a = list(map(int,input().split()))
if n>=2*k:
  a_plus = heapq.nlargest(k, a)
  a_minus = heapq.nsmallest(k, a)
  a_new = a_plus+a_minus
  comb = itertools.combinations(a_new,k)
else:
  comb = itertools.combinations(a,k)
  
l = []
for i in comb:
  l.append(list(i))
  
A = []
one = [1]*len(l)
for i in range(len(l)):
  for j in range(k):
    one[i]*=l[i][j]
    A.append(one[i])
    
l_max = max(one)
waru = 10**9 + 7
 
mod = l_max % waru
print(mod)

### FIXED CODE ###

import sys
 
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = pow(10, 9)+7
zero = 0
plus = []
minus = []
for i in range(n):
  if a[i] == 0:
    zero += 1
  elif a[i] > 0:
    plus.append(a[i])
  else:
    minus.append(a[i])
 
P, M = len(plus), len(minus)
plus.sort(reverse=True)
minus.sort()
ans = 1
if n == k:
  for i in range(n):
    ans *= a[i]
    ans %= mod
elif P+M < k:
  ans = 0
elif P == 0:
  if zero and k%2:
    ans = 0
  else:
    if k%2:
      minus.reverse()
    for i in range(k):
      ans *= minus[i]
      ans %= mod
else:
  q = 0
  if k%2:
    ans *= plus[0]
    ans %= mod
    q = 1
  judge = []
  for i in range((len(plus)-q)//2):
    judge.append(plus[2*i+q]*plus[2*i+q+1])
  for i in range(len(minus)//2):
    judge.append(minus[2*i]*minus[2*i+1])
  judge.sort(reverse=True)
  for i in range(k//2):
    ans *= (judge[i]%mod)
    ans %= mod
 
print(ans)
### BUGGY CODE ###

from fractions import gcd
def lcm(nums):
    ret = 1
    for i in nums:
        ret = ret*i//gcd(ret, i)
    return ret

n,m = map(int, input().split())
a = list(map(int, input().split()))
b = [i//2 for i in a]
g = lcm(b)
if any((g//i)%2==0 for i in b):
    ans = 0
else:
    ans = (m//g+1)//2
print(ans)

### FIXED CODE ###

from fractions import gcd
def lcm(nums):
    ret = 1
    for i in nums:
        ret = ret*i//gcd(ret, i)
        if ret>m:
            return m+1
    return ret

n,m = map(int, input().split())
a = list(map(int, input().split()))
b = [i//2 for i in a]
g = lcm(b)
if any((g//i)%2==0 for i in b):
    ans = 0
else:
    ans = (m//g+1)//2
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 0
count_list = []
A_sl = list(set(A))
if len(A_sl) == 1:
    print(len(A))
elif len(A_sl) == 2:
    if A_sl[1] - A_sl[0] <= 2:
        print(len(A))
    else:
        count_l = A.count(A_sl[1])
        count_s = A.count(A_sl[0])
        print(max(count_l,count_s)) 
else:
    for i in range(min(A),max(A) + 1):
        if i in A_sl:
            count_i = A.count(i)
        else:
            count_i = 0
        count_list.append(count_i)
    for i in range(1,max(A)-min(A)):
        count = count_list[i-1] + count_list[i] + count_list[i+1]
        if count > ans:
            ans = count
    print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
l = [0]*(10**5)
for e in A:
    if e == 0:
        l[0] += 1
        l[1] += 1
    elif e == 99999:
        l[99999] += 1
        l[99998] += 1
    else:
        l[e-1] += 1
        l[e] += 1
        l[e+1] += 1
print(max(l))
### BUGGY CODE ###

MOD = 10 ** 9 + 7

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

ans = 0
total = pow(2, n, MOD)


def comb(n, k):
    bunshi = 1
    bunbo = 1
    for i in range(k):
        bunshi *= n - i
        bunbo *= i+1
        bunshi %= MOD
    return (bunshi * pow(bunbo, MOD-2, MOD)) % MOD


ans = total - (comb(n, a) + comb(n, b)) - 1
print(ans % MOD)


### FIXED CODE ###

MOD = 10 ** 9 + 7

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

ans = 0
total = pow(2, n, MOD)


def comb(n, k):
    bunshi = 1
    bunbo = 1
    for i in range(k):
        bunshi *= n - i
        bunbo *= i+1
        bunshi %= MOD
        bunbo %= MOD
    return (bunshi * pow(bunbo, MOD-2, MOD)) % MOD


ans = total - (comb(n, a) + comb(n, b)) - 1
print(ans % MOD)
### BUGGY CODE ###

from collections import deque

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
dist = [[-1]*w for _ in range(h)]  # 黒ならdist[i][j]は0、白なら-1

black_cells = deque()

for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            black_cells.append((i, j))
            dist[i][j] = 0

def bfs(black_cells, dist):
    d = 0
    while black_cells:
        h_black, w_black = black_cells.popleft()
        d=dist[h_black][w_black]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h_black+dy
            new_w = w_black+dx
            if new_h < 0 or h <= new_h or new_w < 0 or w <= new_w:
                continue
            if dist[new_h][new_w] == -1:
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return max(sum(dist,[]))

d = bfs(black_cells, dist)
print(d)


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
grid = [input() for i in range(H)]

dist = [[-1]*W for _ in range(H)]

black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h, w))
            dist[h][w] = 0

def bfs(black_cells, dist):
    d = 0
    while black_cells:
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  # セルが白('.')であるのと同義
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

d = bfs(black_cells, dist)
print(d)
### BUGGY CODE ###

import sys
# sys.setrecursionlimit(100000)
from collections import defaultdict


def warshall_floyd(graph: dict, N: int):
    """ graph:
    {node:{node:cost,node:cost,...},
     node:{node:cost,node:cost,...},...}
    """
    INF = float("inf")
    dp = [[INF] * N for _ in range(N)]
    for i in range(N):
        dp[i][i] = 0

    # Step 1: fill dp
    for v1, edges in graph.items():
        for v2, cost in edges.items():
            dp[v1][v2] = cost

    # search
    for k in range(N):  # 中継点
        for i in range(N):  # 始点
            for j in range(N):  # 終点
                dp[i][j] = min(dp[i][k] + dp[k][j], dp[i][j])

    return dp


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


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n = input_int()
    graph = defaultdict(dict)
    for _ in range(n - 1):
        a, b, c = input_int_list()
        graph[a][b] = c
        graph[b][a] = c
    dp = warshall_floyd(graph, n + 1)
    q, k = input_int_list()
    ans = []
    for _ in range(q):
        x, y = input_int_list()
        ans.append(dp[x][k] + dp[k][y])

    for i in ans:
        print(i)

    return


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
# sys.setrecursionlimit(100000)
from collections import defaultdict
from heapq import heappop, heappush


class Dijkstra:
    """Graph input:
    {
    node:{node:cost,node:cost...},
    node:{node:cost,node:cost...},
    ...
    }
    """

    def __init__(self, graph: dict, N: int):
        self.graph = graph
        self.costs = [float("inf")] * N

    def calculate(self, start):
        queue = list()

        # step1: push the start point into the priority queue
        self.costs[start] = 0
        heappush(queue, (0, start))  # (cost,node)

        while queue:
            # step2: get the minimum cost node from unfixed node and fix the cost
            cost_from_start, min_node = heappop(queue)

            # step3: update the direct connected nodes
            for link, cost in self.graph[min_node].items():
                if cost_from_start + cost < self.costs[link]:
                    self.costs[link] = cost_from_start + cost
                    heappush(queue, (self.costs[link], link))

        return self.costs


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


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n = input_int()
    graph = defaultdict(dict)
    for _ in range(n - 1):
        a, b, c = input_int_list()
        graph[a][b] = c
        graph[b][a] = c
    # dp = warshall_floyd(graph, n + 1) O(n**3) => TLD

    q, k = input_int_list()

    solver = Dijkstra(graph, n + 1)
    costs = solver.calculate(k)

    ans = []
    for _ in range(q):
        x, y = input_int_list()
        ans.append(costs[x] + costs[y])
    for i in ans:
        print(i)

    return


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

# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
import random
from collections import deque
from decimal import *

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	A = inputList()

	A.sort()
	A = A[::-1]
	ans = 0
	maxs = 0
	cnt = 0

	ansans = []
	pgt = Queue()
	for i,val in enumerate(A):
		if i == 0:
			pgt.enqueue(val)
		else:
			tmp = pgt.dequeue()
			ansans.append(tmp)

			pgt.enqueue(val)

			if tmp == val:
				pass
			else:
				pgt.enqueue(val)

	print(sum(ansans))


class Queue:
    def __init__(self, queue = None):
        if type(queue) is type([]):
            self.queue = queue
        else:
            self.queue = []

    def enqueue(self, e):
        self.queue.append(e)
        return self.queue

    def dequeue(self):
        try:
            qEl = self.queue[0]
            del self.queue[0]
            return qEl
        except IndexError:
            return None

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
import random
from collections import deque
from decimal import *
import queue

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	A = inputList()

	A.sort()
	A = A[::-1]
	ans = 0
	maxs = 0
	cnt = 0
	fst = True

	ansans = []
	pgt = queue.Queue()
	for i,val in enumerate(A):
		if i == 0:
			pgt.put(val)
		else:
			tmp = pgt.get()
			ansans.append(tmp)

			pgt.put(val)

			if tmp == val:
				pgt.put(val)
			else:
				pgt.put(val)

	#print(ansans)
	print(sum(ansans))


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

n=int(input())
a=[int(input()) for _ in range(n)]
       
cnt=0
tmp=1
already=[]
while True:
    cnt+=1
    already.append(tmp)
    tmp=a[tmp-1]
    if tmp==2:
        print(cnt)
        break
    elif tmp in already[::-1]:
        print(-1)
        break

### FIXED CODE ###

import sys
n=int(input())
a=[int(input()) for _ in range(n)]
       
cnt=0
tmp=1

for i in range(n):
    cnt+=1
    tmp=a[tmp-1]
    if tmp==2:
        print(cnt)
        sys.exit()
print(-1)
### BUGGY CODE ###

N,M = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort(reverse=True)

for _ in range(M):
    A[0] = A[0]//2
    A.sort(reverse=True)

print(sum(A))

### FIXED CODE ###

import heapq
N,M = list(map(int, input().split()))
A = list(map(int, input().split()))
A = list(map(lambda x: x*(-1), A))

heapq.heapify(A)


for _ in range(M):
    a = heapq.heappop(A)
    a = -(-a//2)
    heapq.heappush(A,a)

print(-1*sum(A))
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
k = min(x * y * z, k)
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

ab_results = [i + j for i in a for j in b]
ab_results.sort(reverse=True)

ab_results = ab_results[:k]
results = [i + j for i in c for j in ab_results]
results.sort(reverse=True)
list(map(print, results[:k]))


### FIXED CODE ###

import numpy as np
x, y, z, k = map(int, input().split())
k = min(x * y * z, k)
a = np.array(list(map(int, input().split())))
b = np.array(list(map(int, input().split())))
c = np.array(list(map(int, input().split())))

ab = np.ravel(a + b[:, None])
ab.sort()
abc = np.ravel(c + ab[-k:, None])
abc.sort()
print(np.sum(abc[-k:][::-1].astype(str).astype(object) + "\n"), end="")
### BUGGY CODE ###

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

l.sort()
ans = 0
for i in range(n-2):
  for j in range(i+1,n-1):
    k = n-1
    s = l[i]+l[j]
    while(k > j):
      if l[k] < s:
        ans += k-j
        break
      else:
        k -= 1
print(ans)

### FIXED CODE ###

from bisect import bisect_left#(sorted_list,x)で昇順ソート位置

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

l.sort()
ans = 0
for i in range(n-2):
  for j in range(i+1,n-1):
    s = l[i]+l[j]
    ans += bisect_left(l,s,j+1)-j-1
print(ans)
### BUGGY CODE ###

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

for x in reversed(range((Y//10000)+1)):
  for y in reversed(range(((Y-x*10000)//5000)+1)):
    for z in reversed(range(((Y-x*10000-y*5000)//1000)+1)):
      if 10000*x + 5000*y + 1000*z == Y and x+y+z == N:
        print(x, y, z)
        quit()

print("-1 -1 -1")

### FIXED CODE ###

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

for x in range(N+1):
  for y in range(N-x+1):
    z = N-x-y
    if 10000*x + 5000*y + 1000*z == Y and x+y+z == N:
      print(x, y, z)
      quit()

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

import numpy as np

s = input()
t = input()

len_s = len(s)
len_t = len(t)

dp = np.zeros((len_s+1, len_t+1), dtype = int)

for i in range(len_s):
        for j in range(len_t):
                if s[i] == t[j]:
                        dp[i+1, j+1] = np.maximum( dp[i+1, j+1], dp[i, j] + 1)
                dp[i+1, j+1] = np.maximum(dp[i+1,j+1], dp[i+1,j])
                dp[i+1, j+1] = np.maximum(dp[i+1,j+1], dp[i,j+1])
                # print(dp)

# print(dp[len_s,len_t])

i = len_s
j = len_t
str = ''

while i > 0 and j > 0:
        if dp[i-1, j] == dp[i, j]:
            i -= 1
        elif dp[i, j-1] == dp[i, j]:
            j -= 1
        else:
            str += s[i-1]
            i -= 1
            j -= 1
            
print(str[::-1])


### FIXED CODE ###

s = input()
t = input()

len_s = len(s)
len_t = len(t)

dp = [ [0 for _ in range(len_t+1)] for _ in range(len_s+1) ]

for i in range(len_s):
        for j in range(len_t):
                if s[i] == t[j]:
                    dp[i+1][j+1] = max( dp[i+1][j+1], dp[i][j]+1 )
                dp[i+1][j+1] = max( dp[i+1][j+1], dp[i+1][j] )
                dp[i+1][j+1] = max( dp[i+1][j+1], dp[i][j+1] )

i = len_s
j = len_t
str = ''

while i > 0 and j > 0:
        if dp[i-1][j] == dp[i][j]:
            i -= 1
        elif dp[i][j-1] == dp[i][j]:
            j -= 1
        else:
            str += s[i-1]
            i -= 1
            j -= 1
            
print(str[::-1])
### BUGGY CODE ###

from bisect import bisect_left as b
n=int(input())
a=sorted(list(map(int,input().split())))
s=n-1
c=0
while s>0:
    t=2**(len(bin(a[s]))-2)
    d=b(a,t-a[s])
    if d<s and a[d]==t-a[s]:
        a.pop(d)
        c+=1
        s-=2
    else:
        s-=1
print(c)

### FIXED CODE ###

from collections import defaultdict as d
n=int(input())
a=sorted(list(map(int,input().split())))
b=d(int)
for i in a:
    b[i]+=1
s=n-1
c=0
while s>0:
    if b[a[s]]>0:
        t=2**(len(bin(a[s]))-2)
        b[a[s]]-=1
        if b[t-a[s]]>0:
            b[t-a[s]]-=1
            c+=1
    s-=1
print(c)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
 
n, k, q =map(int, input().split())
a = []
 
for i in range(q):
  a.append(int(input()))
  
m = list([k]*n)
 
for i in a:
  m[i-1]+=1
  for j in range(n):
    m[j]-=1
  
  
for i in range(n):
  if m[i]>0:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

# -*- coding: utf-8 -*-
 
n, k, q =map(int, input().split())
a = [int(input()) for i in range(q)]

p = [0]*(n+1)

for i in range(q):
  p[a[i]] += 1
  

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

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


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

from collections import Counter, defaultdict
c = Counter(a)
n1, n2, n3 = c[1], c[2], c[3]
n0 = c[0]
def glist(*l, fill=None):
    if len(l)==1:
        return [fill]*l[0]
    ll = l[1:]
    return [glist(*ll) for _ in range(l[0])]
dp = glist(301, 301, 301)
dp[0][0][0] = 0
count = [0, 0]
def sub(i1,i2,i3):
    count[0] += 1
    if dp[i1][i2][i3] is not None:
        count[1] += 1
        return dp[i1][i2][i3]
    ans = n
    if i1>0:
        ans += i1 * sub(i1-1,i2,i3)
    if i2>0:
        ans += i2 * sub(i1+1,i2-1,i3)
    if i3>0:
        ans += i3 * sub(i1,i2+1,i3-1)
    ans = ans/(i1+i2+i3)
    dp[i1][i2][i3] = ans
    return ans
print(sub(n1,n2,n3))

### FIXED CODE ###

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


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

from collections import Counter, defaultdict
c = Counter(a)
n1, n2, n3 = c[1], c[2], c[3]
n0 = c[0]
def glist(*l, fill=None):
    if len(l)==1:
        return [fill]*l[0]
    ll = l[1:]
    return [glist(*ll) for _ in range(l[0])]

count = 0
S = sum(a)
sub = glist(n1+n2+n3+1,n2+n3+1,n3+1)
sub[0][0][0] = 0
#     for i1 in range(min(n+1, s+1)):
#         for i2 in range(min(n+1, (s-i1)//2+1)):
for i3 in range(n3+1):
    for i2 in range(n2+n3+1-i3):
        for i1 in range(n1+n2+n3 - (i2+i3) + 1):
            if i1==i2==i3==0 or i1+i2+i3>n:
                continue
#             print(i1,i2,i3)
            ans = n
            p = 0
            if i1>0:
                ans += i1 * sub[i1-1][i2][i3]
                p += i1
            if i2>0:
                ans += i2 * sub[i1+1][i2-1][i3]
                p += i2
            if i3>0:
                ans += i3 * sub[i1][i2+1][i3-1]
                p += i3
            ans = ans/p
            sub[i1][i2][i3] = ans
print(sub[n1][n2][n3])
### BUGGY CODE ###

n = int(input())
s = input()
dic = {'R':0,'G':1,'B':2}

lst = []
t_last = (0,0,0)
for i in s[::-1]:
    if i=='R':
        t = (t_last[0]+1, t_last[1], t_last[2])
        lst.append(t)
        t_last = t
    elif i=='G':
        t = (t_last[0], t_last[1]+1, t_last[2])
        lst.append(t)
        t_last = t
    elif i=='B':
        t = (t_last[0], t_last[1], t_last[2]+1)
        lst.append(t)
        t_last = t
lst.reverse()

res = 0
for ni,i in enumerate(s[:-2]):
    lst3 = ['R','G','B']
    lst3.remove(i)
    res += lst[ni][dic[lst3[0]]] * lst[ni][dic[lst3[1]]]
    for nj in range(ni+1,n):
        nk = nj + (nj - ni)
        if nk < n:
            if set(lst3) == set([s[nj],s[nk]]):
                res -= 1
        else:
            break
print(res)

### FIXED CODE ###

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

res = s.count('R') * s.count('G') * s.count('B')

for i in range(n):
    for j in range(i+1, n-1):
        k = j + (j - i)
        if k < n:
            if s[i]!=s[j] and s[j]!=s[k] and s[k]!=s[i]:
                res -= 1
        else:
            break

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

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

def get_input() -> tuple:
    """
    標準入力を取得する.

    Returns:\n
        tuple: 標準入力
    """
    # 標準入力を取得
    N, X, M = list(map(int, input().split()))

    return N, X, M


def f(x: int, m: int) -> int:
    """
    xをmで割った余りを返す.

    Args:\n
        x (int): 整数
        m (int): 整数

    Returns:\n
        int: xをmで割った余り
    """
    return x % m


def main(N: int, X: int, M: int) -> None:
    """
    メイン処理.

    Args:\n
        N (int): 整数(1 <= N <= 10^{10})
        X (int): 整数(0 <= X <= M <= 10^5)
        M (int): 整数(0 <= X <= M <= 10^5)
    """
    # 求解処理
    A = [X]
    i = 0
    while True:
        A_next = f(A[-1]**2, M)
        if A_next in set(A):
            i = A.index(A_next)
            break
        else:
            A.append(A_next)

    loop_length = len(A) - i
    loop_cnt = (N - i) // loop_length
    loop_res = (N - i) % loop_length
    ans = sum(A[:i]) + loop_cnt * sum(A[i:]) + sum(A[i: i + loop_res])

    # 結果出力
    print(ans)


if __name__ == "__main__":
    # 標準入力を取得
    N, X, M = get_input()

    # メイン処理
    main(N, X, M)


### FIXED CODE ###

# -*- coding: utf-8 -*-
# 標準入力を取得
N, X, M = list(map(int, input().split()))

# 求解処理
s = {X}
l = [X]
i = 0
while True:
    a = l[-1]**2 % M
    if a in s:
        i = l.index(a)
        break
    else:
        s.add(a)
        l.append(a)

loop_length = len(l) - i
loop_cnt = (N - i) // loop_length
loop_res = (N - i) % loop_length
ans = sum(l[:i]) + loop_cnt * sum(l[i:]) + sum(l[i: i + loop_res])

# 結果出力
print(ans)