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

N = int(input())
L = sorted(list(map(int, input().split())))

def BinaryIndexSearch_floor(p, SL):
	"""
	search the minimum number among the larger numbers than the ginven nymber "n". 
	return the index of it under the list sorted.
	"""
	#SL = sorted(L)
	l = 0
	r = len(SL) - 1

	while True:
		if l == r:
			if SL[l] > p:
				return l
			else:
				return -1
		elif r-l == 1:
			if SL[l] > p:
				return l
			elif SL[r] > p:
				return r
			else:
				return -1

		center = l + ((r-l) // 2)

		if SL[center] <= p:
			l = center + 1
			continue

		else:
			r = center
			continue

def BinaryIndexSearch_ceil(p, SL):
	#SL = sorted(L)
	l = 0
	r = len(SL) - 1

	while True:
		if l == r:
			if SL[l] < p:
				return l
			else:
				return -1
		elif r-l == 1:
			if SL[r] < p:
				return r
			elif SL[l] < p:
				return l
			else:
				return -1
		center = l + ((r-l) // 2)

		if SL[center] < p:
			l = center 
			continue

		else:
			r = center - 1
			continue
ans = 0
for i in range(N-1):
	for j in range(i+1,N):
		wa = L[i] + L[j]
		sa = abs(L[i]-L[j])

		l = BinaryIndexSearch_ceil(wa,L)
		s = BinaryIndexSearch_floor(sa,L)

		oc = 0
		if s <= i <= l:
			oc += 1
		if s <= j <= l:
			oc += 1
		if l >= s:
			ans += max(0, l-s+1-oc)

print(ans//3)

### FIXED CODE ###

N = int(input())
L = sorted(list(map(int, input().split())))

def BinaryIndexSearch_floor(p, SL):
	"""
	search the minimum number among the larger numbers than the ginven nymber "n". 
	return the index of it under the list sorted.
	"""
	#SL = sorted(L)
	l = 0
	r = len(SL) - 1

	while True:
		if l == r:
			if SL[l] > p:
				return l
			else:
				return -1
		elif r-l == 1:
			if SL[l] > p:
				return l
			elif SL[r] > p:
				return r
			else:
				return -1

		center = l + ((r-l) // 2)

		if SL[center] <= p:
			l = center + 1
			continue

		else:
			r = center
			continue

def BinaryIndexSearch_ceil(p, SL):
	#SL = sorted(L)
	l = 0
	r = len(SL) - 1

	while True:
		if l == r:
			if SL[l] < p:
				return l
			else:
				return -1
		elif r-l == 1:
			if SL[r] < p:
				return r
			elif SL[l] < p:
				return l
			else:
				return -1
		center = l + ((r-l) // 2)

		if SL[center] < p:
			l = center 
			continue

		else:
			r = center - 1
			continue
ans = 0
for i in range(N-1):
	for j in range(i+1,N):
		wa = L[i] + L[j]
		sa = abs(L[i]-L[j])

		l = BinaryIndexSearch_ceil(wa,L)
		s = BinaryIndexSearch_floor(sa,L)

		oc = 0
		if s <= i <= l:
			oc += 1
		if s <= j <= l:
			oc += 1
		if l >= s:
			ans += max(0, l-s+1-oc)

print(ans//3)
### BUGGY CODE ###

from math import factorial

nm = input().split()
n = int(nm[0])
m = int(nm[1])

f = []

i = 2
j = 0
while (m > 1) and i<=m:
    while m%i == 0:
        m /= i
        j += 1
    if j >= 1:
        f.append(j)
    i += 1
    j = 0

        
ans = 1

for k in f:
    if k > 0:
        ans *= factorial(n+k-1) // (factorial(k) * factorial(n-1))
    
print(int(ans) % (10**9+7))


### FIXED CODE ###

from math import factorial

nm = input().split()
n = int(nm[0])
m = int(nm[1])

f = []

i = 2
j = 0
while (m > 1) and i<=m:
    while m%i == 0:
        m /= i
        j += 1
    if j >= 1:
        f.append(j)
    i += 1
    j = 0

        
ans = 1

for k in f:
    if k > 0:
        ans *= factorial(n+k-1) // (factorial(k) * factorial(n-1))
    
print(int(ans) % (10**9+7))
### BUGGY CODE ###

import math
A,B,N = map(int, input().split())
judge = 0
for i in range(N+1):
  if judge < math.floor(A*i/B) - A*math.floor(i/B):
    judge = math.floor(A*i/B) - A*math.floor(i/B)
print(judge)

### FIXED CODE ###

import math
A,B,N = map(int, input().split())
if B > N:
  a = N
else:
  a = B-1
judge = math.floor(A*a/B) - A*math.floor(a/B)
print(judge)
### BUGGY CODE ###

from collections import deque

class MyClass():    
    def load(self):
        self.n = input()
        self.A = map(int,raw_input().split())
        self.q = input()
        self.M = map(int,raw_input().split())

    def main(self):
        self.load()
        W = map(self.solve,self.M)
        for w in W:
            print w

    def solve(self,m):
        qA = deque(self.A)
        for j in range(self.n):
            w = self.rec(m,list(qA))
            if w:
                break
            qA.popleft()            
        if w:
            return "yes"
        else:
            return "no"

    def rec(self,m,A):
        m_new = m
        if m_new < 0:
            r1 = False
        elif m_new == 0:
            r1 = True
        else:
            if len(A) == 1:
                r1 = False
            else:
                r1 = self.rec(m_new,A[1:])
        m_new = m - A[0]
        if m_new < 0:
            r2 = False
        elif m_new == 0:
            r2 = True
        else:
            if len(A) == 1:
                r2 = False
            else:
                r2 = self.rec(m_new,A[1:])
        if r1 or r2:
            return True
        else:
            return False

if __name__ == "__main__":
    MC = MyClass()
    MC.main()

### FIXED CODE ###

from collections import deque

def main():
    n = input()
    A = deque(map(int,raw_input().split()))
    q = input()
    M = map(int,raw_input().split())

    p = rec([0],A)

    for m in M:
        if m in p:
            print "yes"
        else:
            print "no"

def rec(a,A):
    if len(A) == 0:
        return a
    else:
        y = A.popleft()
        a = a+[x+y for x in a]
        return rec(a,A)

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

import sys
import numpy as np
import random
from decimal import Decimal
import itertools
import re
import bisect
from collections import deque, Counter
from functools import lru_cache

sys.setrecursionlimit(10**9)
INF = 10**13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
def SERIES(n): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ')
def GRID(h,w): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ').reshape(h,-1)[:,:w]
def GRIDfromString(h,w): return np.frombuffer(sys.stdin.buffer.read(), 'S1').reshape(h,-1)[:,:w]
MOD = 1000000007

def main():
	s_list = list(S())
	for t in range(2,len(s_list)+1):
		for i in range(len(s_list)-t+1):
			c = Counter(s_list[i:i+t])
			if c.most_common()[0][1] / t  > 0.5:
				print(i+1, i+t)
				break
		else:
			continue
		break
	else:
		print(-1, -1)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import numpy as np
import random
from decimal import Decimal
import itertools
import re
import bisect
from collections import deque, Counter
from functools import lru_cache

sys.setrecursionlimit(10**9)
INF = 10**13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
def SERIES(n): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ')
def GRID(h,w): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ').reshape(h,-1)[:,:w]
def GRIDfromString(h,w): return np.frombuffer(sys.stdin.buffer.read(), 'S1').reshape(h,-1)[:,:w]
MOD = 1000000007

def main():
	s_list = list(S())
	for t in range(2,min(len(s_list)+1,4)):
		for i in range(len(s_list)-t+1):
			c = Counter(s_list[i:i+t])
			if c.most_common()[0][1] / t  > 0.5:
				print(i+1, i+t)
				break
		else:
			continue
		break
	else:
		print(-1, -1)

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

import sys
from collections import Counter

n = int(sys.stdin.readline())
battle_dict = dict()
cur_stage = Counter([])
new_ls = []
for i in range(n):
    inp = [int(i) for i in sys.stdin.readline().split()]
    battle_dict[i + 1] = inp
    new_ls.append(tuple(sorted([i + 1, inp[0]])))
cur_stage.update(new_ls)

cnt = 0
while True:
    flg = 0
    for v, c in cur_stage.items():
        if c > 1:
            i, j = v
            if len(battle_dict[i]) > 0:
                battle_dict[i].pop(0)
            if len(battle_dict[j]) > 0:
                battle_dict[j].pop(0)
            cur_stage[v] = 0
            flg = 1
    if flg == 0:
        break
    else:
        cnt += 1
    cur_stage.clear()
    new_ls = []
    for i, j in battle_dict.items():
        if len(j) > 0:
            new_ls.append(tuple(sorted([i, j[0]])))
    cur_stage.update(new_ls)
if len(cur_stage) > 0:
    print(-1)
else:
    print(cnt)

### FIXED CODE ###

import sys
from collections import Counter
import copy

n = int(sys.stdin.readline())
ct = Counter()
a_ls = dict()
for i in range(n):
    inp = [int(i) - 1 for i in sys.stdin.readline().split()]
    a_ls[i] = inp
cnt = 0
candidate = list(range(n))
rest = n * (n - 1) / 2
combis = set()
while rest:
    no_ls = []
    next_candidate = []
    flg = False
    for i in candidate:
        if len(a_ls[i]) == 0:
            continue
        target = a_ls[i][0]
        if (i, target) in combis or (target, i) in combis:
            next_candidate.append(i)
            next_candidate.append(target)
            rest -= 1
            if len(a_ls[i]) > 0:
                a_ls[i].pop(0)
            if len(a_ls[target]) > 0:
                a_ls[target].pop(0)
            flg = True
        else:
            combis.add((i, target))
    candidate = next_candidate
    if not flg:
        cnt = -1
        break
    cnt += 1
print(cnt)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)

M = 10**9 + 7
K = int(input())
D = int(input())

dp = [[None] * 100 for _ in range(10**5 + 1)]
def f(k, i):
    if dp[i][k] is not None:
        return dp[i][k]

    if i == 0:
        r = (k % D) == 0
        dp[i][k] = r
        return r
    r = sum(f((k + x) % D, i - 1) for x in range(0, 10)) % M
    dp[i][k] = r
    return r

# dp = [[0] * 100 for _ in range(10**5 + 1)]
# for i in range(10**5 + 1):
#     for k in range(100):
#         if i == 0:
#             dp[i][k] = int((k % D) == 0)
#         else:
#             dp[i][k] = sum(dp[(k + x) % D][i - 1] for x in range(0, 10)) % M
#
# def f(k, i):
#     return dp[i][k]

sk = str(K)
dig = len(sk)
answer = 0
s = sum(map(int, list(sk)))
for j in range(int(sk[-1]) + 1):
    if (s - j) % D == 0:
        answer += 1

if dig > 1:
    s -= int(sk[-1])
    for i in range(dig - 1, 1, -1):
        if sk[i - 1] == "0":
            continue
        for j in range(int(sk[i - 1])):
            answer += f((s - 1) % D - j, dig - i)
        s -= int(sk[i - 1])

    for k in range(1, int(sk[0])):
        answer += f(k % D, dig - 1)

    if dig > 1: # 先頭0固定
        for k in range(10):
            answer += f(k % D, dig - 2)


print((answer - 1) % M)


### FIXED CODE ###

string = input()
d = int(input())

nums = [int(v) for v in string]
length = len(string) - 1
k = int(string)

M = 10**9 + 7
def mod(v):
    if v >= M:
        return v % M
    return v

dp = [[[None] * 2 for _ in range(d)] for _ in range(length + 2)]
def dfs(i=0, s=0, border=True):
    if dp[i][s][border] is not None:
        return dp[i][s][border]

    if i > length:
        r = int(not bool(s))
        dp[i][s][border] = r
        return r

    cnt = 0
    for n in range(max(9 * (not border), nums[i]) + 1):
        cnt = mod(cnt + dfs(i + 1, (s + n) % d, border and nums[i] == n))
    dp[i][s][border] = cnt
    return cnt
# print(mod(dfs() - 1))

for i in reversed(range(length + 2)):
    for s in reversed(range(d)):
        for border in [False, True]:
            if i > length:
                dp[i][s][border] = int(not bool(s))
                continue

            cnt = 0
            for n in range(max(9 * (not border), nums[i]) + 1):
                cnt = mod(cnt + dp[i + 1][(s + n) % d][border and nums[i] == n])
            dp[i][s][border] = cnt

print(mod(dp[0][0][1] - 1 + M))
### BUGGY CODE ###

s = list(input())
n = int(input())
r = 1
for x in range(n):
    q = input().split()
    if q[0] == '1':
        r = -r
    elif q[1] == '1':
        z = q[2][0]
        if r == 1:
            s.insert(0, z)
        else:
            s.append(z)
    else:
        z = q[2][0]
        if r == -1:
            s.insert(0, z)
        else:
            s.append(z)
if r == -1:
    s.reverse()
print("".join(s))


### FIXED CODE ###

s = input()
n = int(input())
x = []
y = []
r = 1
for i in range(n):
    q = input().split()
    if q[0] == '1':
        r = -r
    elif q[1] == '1':
        z = q[2][0]
        if r == 1:
            x.append(z)
        else:
            y.append(z)
    else:
        z = q[2][0]
        if r == -1:
            x.append(z)
        else:
            y.append(z)
if r == 1:
    x.reverse()
    print("".join(x) + s + "".join(y))
else:
    y.reverse()
    print("".join(y) + s[::-1] + "".join(x))
### BUGGY CODE ###

import bisect
import sys
sys.setrecursionlimit(10 ** 8)
n = int(input())
a = list(map(int, input().split()))
edges = [[] for _ in range(n)]
for _ in range(n-1):
    u, v = map(int, input().split())
    edges[u-1].append(v-1)
    edges[v-1].append(u-1)

d = [-1 for _ in range(n)]

def dfs(i, s):
    d[i] = len(s)

    for to in edges[i]:
        if d[to] == -1:
            t = s.copy()
            if t[-1] < a[to]:
                t.append(a[to])
            else:
                t[bisect.bisect_left(t, a[to])] = a[to]

            dfs(to, t)

dfs(0, [a[0]])
for i in range(n):
    print(d[i])


### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 8)

n = int(input())
a = list(map(int, input().split()))
edges = [[] for _ in range(n)]
for _ in range(n-1):
    u, v = map(int, input().split())
    edges[u-1].append(v-1)
    edges[v-1].append(u-1)

inf = 10 ** 10
d = [inf for _ in range(n)]
dp = [inf for _ in range(n)]

def dfs(cur, prev):
    memo = bisect.bisect_left(dp, a[cur])
    memo_v = dp[memo]
    dp[memo] = a[cur]
    d[cur] = bisect.bisect_left(dp, inf)

    for to in edges[cur]:
        if to != prev:
            dfs(to, cur)

    dp[memo] = memo_v

dfs(0, -1)
for i in range(n):
    print(d[i])
### BUGGY CODE ###

n = int(raw_input())
A = map(int, raw_input().strip().split(' '))
q = int(raw_input())
M = map(int, raw_input().strip().split(' '))

memo = []
for i in range(len(A)+1):
    memo.append([None]*2000)

def solve(i,m):
    if memo[i][m] != None: return memo[i][m]
    if m == 0:
        memo[i][m] = True
        return True
    elif i >= n:
        memo[i][m] = False
        return False
    else:
        return solve(i+1,m) | solve(i+1,m-A[i])

for m in M:
    if solve(0,m): print "yes"
    else: print "no"

### FIXED CODE ###

n = int(raw_input())
A = map(int, raw_input().strip().split(' '))
q = int(raw_input())
M = map(int, raw_input().strip().split(' '))

memo = []
for i in range(len(A)+1):
    memo.append([None]*2000)

def solve(i,m):
    if memo[i][m] != None: return memo[i][m]
    if m == 0:
        memo[i][m] = True
        return True
    elif i >= n:
        memo[i][m] = False
        return False
    else:
        ret = solve(i+1,m) | solve(i+1,m-A[i])
        memo[i][m] = ret
        return ret

for m in M:
    if solve(0,m): print "yes"
    else: print "no"
### BUGGY CODE ###

#L
import sys
sys.setrecursionlimit(10**5)

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

S=[0]*(N+1)
for i in range(N):
    S[i+1]=S[i]+a[i]

dp=[[0]*(N+1) for _ in range(N+1)]#[l,r)の範囲が残っているときに取れる最大値

def rep(l,r):
    if l==r:
        return 0
    if dp[l][r]!=0:
        return dp[l][r]
    else:
        x=a[l]+(S[r]-S[l+1] - rep(l+1,r))
        y=a[r-1]+(S[r-1]-S[l] - rep(l,r-1))
        dp[l][r]=max(x,y)
        return dp[l][r]
    
    
rep(0,N)
print(2*dp[0][N] - S[-1] )








### FIXED CODE ###

#L

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

S=[0]*(N+1)
for i in range(N):
    S[i+1]=S[i]+a[i]

dp=[[0]*(N+1) for _ in range(N+1)]#[l,r)の範囲が残っているときに取れる最大値

for i in range(1,N+1):#r-lの値
    for j in range(N):#lの値
        r=j+i
        if r>N:
            break
        l=j
        x=a[l]+(S[r]-S[l+1]) - dp[l+1][r]
        y=a[r-1]+(S[r-1]-S[l]) - dp[l][r-1]
        dp[l][r]=max(x,y)

print(2*dp[0][N] - S[-1] )
### BUGGY CODE ###

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


ans = 0
f = True
while f:
    f = False
    for i in range(N):
        a,b,c = B[(i-1)%N],B[i],B[(i+1)%N]
        if b > a+c and b > A[i]:
            ans += (b-A[i])//(a+c)
            B[i] = A[i]//(a+c)*(a+c)+B[i]%(a+c) 
            f = True

if A != B:
    ans = -1
print(ans)

### FIXED CODE ###

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


ans = 0
f = True
while f:
    f = False
    for i in range(N):
        a,b,c = B[(i-1)%N],B[i],B[(i+1)%N]
        if b > a+c and b > A[i]:
            if (b-A[i])%(a+c)==0:
                B[i] = A[i]
                ans += (b-A[i])//(a+c)
            else:
                ans += B[i]//(a+c)
                B[i] %= a+c
            f = True

if A != B:
    ans = -1
print(ans)
### BUGGY CODE ###

from math import gcd
import numpy as np

n = int(input())
a = list(map(int, input().split()))
MAX = 10 ** 6

g = a[0]
for e in a:
    g = gcd(g, e)

if g != 1:
    print("not coprime")
    exit()

nums = np.zeros(MAX + 1, np.int64)
for e in a:
    nums[e] += 1
for i in range(2, MAX + 1):
    if nums[i::i].sum() > 1:
        print("setwise coprime")
        exit()

print("pairwise coprime")



### FIXED CODE ###

from math import gcd
import numpy as np
from numba import njit

n = int(input())
a = list(map(int, input().split()))
MAX = 10 ** 6

g = a[0]
for e in a:
    g = gcd(g, e)

if g != 1:
    print("not coprime")
    exit()

nums = np.zeros(MAX + 1, np.int64)
for e in a:
    nums[e] += 1


@njit
def f(nums):
    for i in range(2, MAX + 1):
        if nums[i::i].sum() > 1:
            return False

    return True


bl = f(nums)

if bl:
    print("pairwise coprime")
else:
    print("setwise coprime")
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in a[:n-1]:
    ans += i*(sum(a[a.index(i)+1:]))
print(ans%(10**9+7))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
r = sum(a)
for i in a[:n-1]:
    r = r - i
    ans = (ans+i*r)%(10**9+7)
print(ans)
### BUGGY CODE ###

A,B = map(int,input().split())
C = []
ans = 1
mid = int(max(A,B)/2)
for i in range(2,mid+2):
    if A % i== 0 and B % i == 0:
        for j in range(2,i+1):
            if j == i:
                ans += 1
            elif i % j == 0:
                break
print(ans)

### FIXED CODE ###

import math

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

A,B = map(int,input().split())
a = prime_factorize(A)
b = prime_factorize(B)
ans = 1

while a != []:
    x = a[0]
    if x in b:
        ans+=1
    a = [i for i in a if i != x]

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

N = int(input())
A = list(map(int, input().split()))
list_st = []
for i in range(N):
  print(A.index(i+1)+1)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
B = [0]*n
for i in range(n):
  B[A[i]-1] = i + 1 
for i in range(n):
  print(B[i])
### BUGGY CODE ###

def isprime(x):
    if x == 2: return True
    if x % 2 == 0: return False
    for i in range(3, x, 2):
        if x % i == 0: return False
    return True

n = int(input())
count = 0
for i in range(n):
    x = int(input())
    if isprime(x): count += 1
print(count)

### FIXED CODE ###

import math

def isprime(x):
    if x == 2: return True
    if x % 2 == 0: return False
    for i in range(3, math.ceil(math.sqrt(x)) + 1, 2):
        if x % i == 0: return False
    return True

n = int(input())
count = 0
for i in range(n):
    x = int(input())
    if isprime(x): count += 1
print(count)
### BUGGY CODE ###

# E - Crested Ibis vs Monster
def main():
    INF = 1 << 30

    H, N, *AB = map(int, open(0).read().split())
    dp = [INF] * (H + 10001)  # dp[i] := min magic points to decrease monster's health by i
    dp[0] = 0
    for i in range(H):
        if dp[i] == INF:
            continue
        for a, b in zip(*[iter(AB)] * 2):
            dp[i + a] = min(dp[i + a], dp[i] + b)
    print(min(dp[H:]))


if __name__ == "__main__":
    main()


### FIXED CODE ###

# E - Crested Ibis vs Monster
from collections import defaultdict


def main():
    H, N, *AB = map(int, open(0).read().split())
    dp = defaultdict(lambda: 1 << 30)  # dp[i] := min magic points to decrease monster's health by i
    dp[0] = 0
    for a, b in zip(*[iter(AB)] * 2):
        for i in range(H):
            if i not in dp:
                continue
            dp[i + a] = min(dp[i + a], dp[i] + b)
    ans = min(magic for health, magic in dp.items() if health >= H)
    print(ans)


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

from sys import stdin
n = int(stdin.readline().rstrip())
data = [stdin.readline().rstrip() for _ in range(n)]

s = []
cnt = [0] * n
_max = 0
for tmp in data:
  if tmp not in s:
    s.append(tmp)
  cnt[s.index(tmp)] += 1
  if _max < cnt[s.index(tmp)]:
    _max = cnt[s.index(tmp)]
    
results = []
for i in range(len(s)):
  if cnt[i] == _max:
    results.append(s[i])

results.sort()
for result in results:
  print(result)

### FIXED CODE ###

n = int(input())

dic = {}
for i in range(n):
  s = input()
  if s in dic:
    dic[s] += 1
  else:
    dic[s] = 1

_max = 0
for v in dic.values():
  if _max < v:
    _max = v
dic2 = sorted(dic.items())

for (k,v) in dic2:
  if v == _max:
    print(k)
### BUGGY CODE ###

n = int(input())
list_S = list(input())
list_R = []
list_B = []
list_G = []
ans = 0
for i, c in enumerate(list_S):
    if c == "R":
        list_R.append(i+1)
    if c == "B":
        list_B.append(i+1)
    if c == "G":
        list_G.append(i+1)
 
for i in list_R:
    for j in list_G:
        for k in list_B:
            l = [i,j,k]
            l.sort()
            if l[1]-l[0] != l[2]-l[1]:
                ans += 1
 
print(ans)

### FIXED CODE ###

n = int(input())
list_S = list(input())
list_R = []
list_B = []
list_G = []
ans = 0
for i, c in enumerate(list_S):
    if c == "R":
        list_R.append(i+1)
    if c == "B":
        list_B.append(i+1)
    if c == "G":
        list_G.append(i+1)
set_R = set(list_R)
set_G = set(list_G)
set_B = set(list_B)
cnt = 0
for i in list_R:
    for j in list_G:
        max_value = max(i, j)
        min_value = min(i, j)
        d = (max_value - min_value)
        if d % 2 == 0:
            if max_value-d//2 in set_B:
                cnt += 1

        if max_value+d in set_B:
            cnt += 1
        if min_value-d in set_B:
            cnt += 1
        ans += len(set_B)

print(ans-cnt)