Harryxun/stf_run huggingface dataset:
"""
K = int(input())

def gcd(a, b): # 最大公約数
    a = abs(a)
    b = abs(b)
    while b:
        a, b = b, a % b
    return a # int
ans = 0
for i in range(1,K+1):
    for j in range(i,K+1):
        for k in range(j,K+1):
            d = gcd(gcd(i,j),k)
            if i==j==k:
                ans += d
            elif i==j or j== k or k==i:
                ans += 3*d
            else:
                ans += 6*d
print(ans)
"""
N = int(input())
S = input()
R = []
G = []
B = []
import bisect
for i in range(N):
    if S[i] == 'R':
        R.append(i)
    elif S[i] == 'G':
        G.append(i)
    else:
        B.append(i)
ans = 0
for rr in R:
    for gg in G:
        
        r = min(rr,gg)
        g = max(rr,gg)
        if 2*r-g>=0:
            if 2*r-g == B[bisect.bisect_left(B,2*r-g)]:
                ans -=1
        
        if 2*g-r < N:
            #print(rr,gg,bisect.bisect_left(B,2*g-r))
            if 2*g-r == B[bisect.bisect_left(B,2*g-r)]:
                ans -=1
        
        if (g+r)%2==0 and (g+r)//2 == B[bisect.bisect_left(B,(g+r)//2)]:
            ans -= 1
        ans += len(B)
        
print(ans)
        


### FIXED CODE ###


"""
K = int(input())

def gcd(a, b): # 最大公約数
    a = abs(a)
    b = abs(b)
    while b:
        a, b = b, a % b
    return a # int
ans = 0
for i in range(1,K+1):
    for j in range(i,K+1):
        for k in range(j,K+1):
            d = gcd(gcd(i,j),k)
            if i==j==k:
                ans += d
            elif i==j or j== k or k==i:
                ans += 3*d
            else:
                ans += 6*d
print(ans)
"""
N = int(input())
S = input()
R = []
G = []
B = []
import bisect
for i in range(N):
    if S[i] == 'R':
        R.append(i)
    elif S[i] == 'G':
        G.append(i)
    else:
        B.append(i)
ans = 0
for rr in R:
    for gg in G:
        
        r = min(rr,gg)
        g = max(rr,gg)
        if 2*r-g>=0:
            id = bisect.bisect_left(B,2*r-g)
            if id < len(B) and 2*r-g == B[id]:
                ans -=1
        
        if 2*g-r < N:
            id = bisect.bisect_left(B,2*g-r)
            if id < len(B) and 2*g-r == B[id]:
                ans -=1
        
        if (g+r)%2==0:
            id = bisect.bisect_left(B,(g+r)//2)
            if id < len(B) and (g+r)//2 == B[id]:
                ans -= 1
        ans += len(B)
        
print(ans)
def insertion(A, n, g):
    c = 0
    for i in range(g, n):
        key = A[i]
        j = i - g
        while j >= 0 and A[j] > key:
            A[j + g] = A[j]
            j -= g
            c += 1
        A[j + g] = key
    return c

def main():
    n = input()
    A = [input() for i in range(n)]

    G = list()
    h = 1
    while h <= n:
        G[0:0] = [h]
        h = 3 * h + 1
    cnt = 0

    for i in G:
        cnt += insertion(A, n, i)

    print(len(G))
    print(" ".join(map(str, G)))
    print(cnt)
    for k in A: print(k)

main()

### FIXED CODE ###

def insertion(A, n, g):
    cnt = 0
    for i in range(g, n):
        while i >= g and A[i - g] > A[i]:
            A[i], A[i - g] = A[i - g], A[i]
            i -= g
            cnt += 1
    return cnt

def main():
    n = int(raw_input())
    A = [int(raw_input()) for i in range(n)]

    G = list()
    h = k = 1
    while h <= n:
        G.append(h)
        h = (4 ** k) + (3 * (2 ** (k - 1)) + 1)
        k += 1
    G = G[::-1]

    cnt = 0
    for i in G:
        cnt += insertion(A, n, i)

    print(len(G))
    print(" ".join(map(str, G)))
    print(cnt)
    for j in A: print(j)

main()
n = int(input())
height = list(map(int, input().split()))
li = []
max_height = max(height)
for i in range(n - 1):
    sl = height[i + 1:]
    if sl == sorted(sl,reverse=True):
        count = len(sl)-1
        break
    else:
        pass
print(count)


### FIXED CODE ###

n = int(input())
c = 0
l = []
li = list(map(int, input().split()))
for i in range(1, n):
	if li[i-1] >= li[i]:
		c += 1
		#print('k', li[i])
	else:
		#print(li[i])
		l.append(c) 
		c = 0
l.append(c)
print(max(l))
def insertionSort(arr, N, g):
    cnt = 0
    for i in range(g, N):
        tmp = arr[i]
        j = i - g
        while(j >= 0 and arr[j] > tmp):
            arr[j + g] = arr[j]
            j -= g
            cnt += 1
        arr[j + g] = tmp
    return cnt


def shellSort(arr, N):
    cnt = 0
    G = []
    h = 0
    m = 0
    while h <= N / 9:
        h = 3 * h + 1
        G.append(h)
        m += 1
    G = G[::-1]

    cnt = sum([insertionSort(arr, N, g) for g in G])
    return (cnt, g)


N = int(input())
arr = [int(input()) for i in range(N)]

(cnt, G) = shellSort(arr, N)
print(len(G), ' '.join(map(str, G)), cnt, '\n'.join(map(str, arr)), end='\n')



### FIXED CODE ###

def insertionSort(arr, N, g):
    cnt = 0
    for i in range(g, N):
        tmp = arr[i]
        j = i - g
        while(j >= 0 and arr[j] > tmp):
            arr[j + g] = arr[j]
            j -= g
            cnt += 1
        arr[j + g] = tmp
    return cnt


def shellSort(arr, N):
    G = []
    h = 0
    m = 0
    while h <= N / 9:
        h = 3 * h + 1
        G.append(h)
        m += 1
    G = G[::-1]

    cnt = sum([insertionSort(arr, N, g) for g in G])
    return (cnt, G)


N = int(input())
arr = [int(input()) for i in range(N)]

(cnt, G) = shellSort(arr, N)
print(len(G))
print(' '.join(map(str, G)))
print(cnt)
print('\n'.join(map(str, arr)))
def rl(proc=None):
    if proc is not None:
        return proc(sys.stdin.readline())
    else:
        return sys.stdin.readline().rstrip()

def srl(proc=None):
    if proc is not None:
        return map(proc, rl().split())
    else:
        return rl().split()

def fix(a):
    mn = min(a) - 1
    return [x - mn for x in a]

def main():
    N = rl(int)
    p = srl(int)
    a = range(N)
    b = list(reversed(a))
    for i, v in enumerate(p[1:], 1):
        a[v-1] += i
        for j in xrange(v, N):
            a[j] += i
            b[j] -= i
    print " ".join(map(str, fix(a)))
    print " ".join(map(str, fix(b)))

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

def rl(proc=None):
    if proc is not None:
        return proc(sys.stdin.readline())
    else:
        return sys.stdin.readline().rstrip()

def srl(proc=None):
    if proc is not None:
        return map(proc, rl().split())
    else:
        return rl().split()

def fix(a):
    mn = min(a) - 1
    return [x - mn for x in a]

def main():
    N = rl(int)
    p = srl(int)
    a = range(N)
    b = list(reversed(a))
    inc = [0] * (N+1)
    for i, v in enumerate(p[1:], 1):
        a[v-1] += i
        inc[v] += i
    s = 0
    for i in xrange(N):
        s += inc[i]
        a[i] += s
        b[i] -= s
    print " ".join(map(str, fix(a)))
    print " ".join(map(str, fix(b)))

if __name__ == '__main__':
    main()
import sys
input = sys.stdin.readline

N = int(input())

if N%2:
    print(0)
else:

    ans = (N//10) + (N//50)+ (N//200) - ((N//10)//(N//50))
    print(ans)



### FIXED CODE ###

# coding: utf-8
# Your code here!

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    
    # 奇数は終わる
    if N%2:
        print('0')
        quit()
    
    def calc(x,ans):
        fl = 2*(5**x)
        if N >= fl:
            ans += N//fl
            return calc(x+1,ans)
        else:
            return ans
    
    print(calc(1, 0))
        
    
    
if __name__ == '__main__':
    main()
a=int(input())
a.remove("/","")
print("Heisei" if a<=2019430 else "TBD")

### FIXED CODE ###

a=input()
print("Heisei" if int(a.replace("/", ""))<=20190430 else "TBD")
n = int(raw_input())
l = []
max = -10^9
x=0
for i in range(n-1):
    l.append(int(raw_input())

for s in range(n-1):
 for t in range(s-1):
  x= l[n-s-1] - l[n-t-1]
  if max<x:
   max=x
printf'%d'%(max)

### FIXED CODE ###

n = int(raw_input())
max = -10**9
x1 = input() 
min = x1

for i in range(n-1):
 x = int(raw_input())

 if max < x-min:
  max = x- min
 if x< min:
  min = x
  
print max
A,B,C,K=map(input().split())
if A>=K:
  print(K)
elif A+B>=K:
  print(A)
else:
  print(A+A+B-K)

### FIXED CODE ###

A,B,C,K=map(int,input().split())
if A>=K:
  print(K)
elif A+B>=K:
  print(A)
else:
  print(A+A+B-K)
n, m = map(int, input().split())
h = list(map(int, input().split()))
g = [[] for _ in range(n)]
t = [-1 for _ in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)

def dfs(i):
    if t[i] != -1:
        return
    else:
        t[i] = 1
    for j in g[i]:
        if h[i] <= h[j]:
            t[i] = 0
        dfs(j)

for i in range(n):
    dfs(i)
ans = n
for i in t:
    if i == 0:
        ans -= 1
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
h = list(map(int, input().split()))
t = [1 for _ in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if h[a] > h[b]:
        t[b] = 0
    elif h[a] == h[b]:
        t[a] = 0
        t[b] = 0
    else:
        t[a] = 0
ans = 0
for i in t:
    if i==1:
        ans += 1
print(ans)
from math import gcd
a,b,c = map(int, input().split())
if gcd(a,b)%c==0:
  print('Yes')
  exit()
print('No')

### FIXED CODE ###

from fractions import gcd
a,b,c = map(int, input().split())
if c%gcd(a,b)==0:
  print('YES')
  exit()
print('NO')
# coding: utf-8
# A - Fifty-Fifty

s = input()
c = []
dict = {}
for i in s:
    if i in dict:
        dict[i] +=1
    else:
        dict[i] = 1
        c.append(i)
if dict[c[0]] == dict[c[1]]:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

# coding: utf-8
# A - Fifty-Fifty

s = input()
c = []
dict = {}
for i in s:
    if i in dict:
        dict[i] +=1
    else:
        dict[i] = 1
        c.append(i)

if dict[c[0]] == 4:
    print("No")
elif dict[c[0]] == dict[c[1]] == 2 and len(dict) == 2:
    print("Yes")
else:
    print("No")
def f(D):
    i = 0
    s = 0
    D = D[D.index("1"):]
    for c in D:
        if c=="1": s += i
        i += 1
    p = "ABCDEFG"[ptn.index(s)]
    return p
 
i=0
D=""
for s in sys.stdin:
    if i<8:
        i+=1
        D+=s[:-1]
    else:
        print f(D)
        i=0
        D=""
print f(D)

### FIXED CODE ###

import sys
ptn = [18,48,6,30,20,34,16]

def f(D):
    i = 0
    s = 0
    D = D[D.index("1"):]
    for c in D:
        if c=="1": s += i
        i += 1
    p = "ABCDEFG"[ptn.index(s)]
    return p

i=0
D=""
for s in sys.stdin:
    if i<8:
        i+=1
        D+=s[:-1]
    else:
        print f(D)
        i=0
        D=""
print f(D)
LARGE = 1000000007


def step(a, i):
    if i == len(a):
        return 1
    elif i > len(a):
        return 0

    elif a[i] == 0:
        return 0

    return step(a, i + 1) + step(a, i + 2)


def solve():
    n, m = [int(x) for x in input().split()]
    a = [1] * n
    for _ in range(m):
        a[int(input())] = 0

    # print(n, m)
    # print(a)

    ans = step(a, 0)
    print(ans % LARGE)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

# inputs
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]

# solve
dp = [1] * (n+1)

for i in a:
    dp[i] = 0

for i in range(2, n+1):
    if dp[i] != 0:
        dp[i] = (dp[i - 1] + dp[i - 2]) % (10 ** 9 + 7)

print(dp[n])
def main(n, a):
    indexes = {i + 1 for i in range(n)}
    reduced = set()
    for s in a:
        reduced |= s
    return len(indexes - reduced)


if __name__ == '__main__':
    S = input().rstrip()
    N, K = map(int, input().split())
    A = []
    for _ in range(K):
        input()
        A.append(set(tuple(map(int, input().split(' ')))))
    print(main(N, A))


### FIXED CODE ###

def main(n, a):
    indexes = {i + 1 for i in range(n)}
    reduced = set()
    for s in a:
        reduced |= s
    return len(indexes - reduced)


if __name__ == '__main__':
    N, K = map(int, input().split())
    A = []
    for _ in range(K):
        input()
        A.append(set(tuple(map(int, input().split(' ')))))
    print(main(N, A))
n,m = map(int, input().split())
H = list(map(int, input().split()))
S = []
c = 0
b = []

for i in range(m):
    S.append(list(map(int, input()split())))

for j in range(n):
    for k in range(m):
        if j in S[k]:
            if S[k][0] == j:
                if S[k][0] < S[k][1]:
                    c += 1
            else:
                if S[k][0] > S[k][1]:
                    c + = 1
    if c ==0:
        b.append(j)

print(len(b))

### FIXED CODE ###

n, m = map(int, input().split())
h = list(map(int, input().split()))
sore = [[0] for i in range(n)]
for i in range(m):
    road = list(map(int, input().split()))
    sore[road[0]-1].append(h[road[1]-1])
    sore[road[1]-1].append(h[road[0]-1])
ans = 0
for i in range(n):
    if h[i] > max(sore[i]):
        ans+=1
print(ans)
k,x=map(int,input().split())
print("Yes" if 500*k>=x "No" else)

### FIXED CODE ###

k,x=map(int,input().split())
print("Yes" if 500*k>=x else "No" )
while True:
    n = int(input())
    if n == 0:
        break
    c = 0
    for i in range(2, 1001):
        for a in range(1, 1001):
            if i*a+(0.5*(i-1)*i) == n:
                c += 1
    print(c)



### FIXED CODE ###

while True:
    n = int(input())
    if n == 0:
        break
    c = 0
    for i in range(2, 1001//2):
        for a in range(1, 1001//2):
            if i*a+(0.5*(i-1)*i) == n:
                c += 1
    print(c)
X = int(input())

Dp = [False for _ in range(X+1)]

Dp[0] = True
for i in range(X+1):
    if any([Dp[i - j] == True for j in range(100, 107)]):
        Dp[i] = True
if Dp[X]:
    print(1)
else:
    print(0)

### FIXED CODE ###

X = int(input())

Dp = [False for _ in range(X+1)]

Dp[0] = True
for i in range(100, X+1):
    if any([Dp[i - j] == True for j in range(100, 106)]):
        Dp[i] = True
if Dp[X]:
    print(1)
else:
    print(0)
l=input().split()
a=int(l[0])
b=int(l[1])
if a%b==0:
    print(a+b)
elif:
    print(b-a)

### FIXED CODE ###

l=input().split()
a=int(l[0])
b=int(l[1])
if b%a==0:
    print(a+b)
else:
    print(b-a)
x = input()
print(x**3)

### FIXED CODE ###

x = int(input())
print(x**3)
#!/usr/bin/env python3

import math

n = int(input())
a = input().split()
num1 = 10000000000
num2 = 10000000000

for i in range(n-1):
    w = math.gcd(int(a[i]),int(a[i+1]))
    if w < num1:
        num1 = w
    elif num1 <= w <= num2:
        num2 = w

if num2 == 10000000000:
    print(num1)
else:
    print(num2)
    


### FIXED CODE ###

#!/usr/bin/env python3

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

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

memo1 = 10**9
memo2 = 10**9

lf = [0 for i in range(n)]
rgt = [0 for i in range(n)]

lf[0] = a[0]
rgt[0] = a[n-1]

for i in range(1,n):
	lf[i] = gcd(lf[i-1],a[i])
	rgt[i] = gcd(rgt[i-1],a[i*(-1)-1])


mx = 0
mx = max(mx,lf[n-2])
mx = max(mx,rgt[n-2])

for i in range(1,n-1):
	mx = max(mx,gcd(lf[i-1],rgt[i*(-1)-2]))

print(mx)
n, k = map(int,input().split())
a = [int(i) for i in input().split()]

if n == k:
    cnt == 1
else:
    cnt = (n - k) // (k-1) + 2
print(cnt)

### FIXED CODE ###

n, k = map(int,input().split())
a = [int(i) for i in input().split()]

if n == k:
    cnt = 1
else:
    cnt = (n - 2) // (k-1) + 1
print(cnt)
import numpy as np

H, W, M = map(int, input().split())
h = np.zeros((H))
w = np.zeros((W))
m = np.zeros((H, W))
ans = 0
for _ in range(M):
    tmp_h, tmp_w = map(int, input().split())
    h[tmp_h-1] += 1
    w[tmp_w-1] += 1
    m[tmp_h-1, tmp_w-1] = 1.

'''
h_max = np.max(h)
h_max_index = list(zip(*np.where(h == h_max)))
w_max = np.max(w)
w_max_index = list(zip(*np.where(w == w_max)))

for i in h_max_index:
    for j in w_max_index:
        if m[i[0]][j[0]] == 1.:
            tmp = h_max + w_max -1
        else:
            tmp = h_max + w_max
        if ans < tmp:
            ans = tmp
'''
print(int(ans))


### FIXED CODE ###

import numpy as np

H, W, M = map(int, input().split())
h = np.zeros(H)
w = np.zeros(W)
m = {}
flag = 0

for _ in range(M):
    tmp_h, tmp_w = map(int, input().split())
    h[tmp_h-1] += 1
    w[tmp_w-1] += 1
    m[(tmp_h-1, tmp_w-1)] = 1.

h_max = np.max(h)
h_max_index = list(zip(*np.where(h == h_max)))
w_max = np.max(w)
w_max_index = list(zip(*np.where(w == w_max)))

for i in h_max_index:
    for j in w_max_index:
        if (i[0], j[0]) not in m.keys():
            flag = 1
            break

if flag == 1:
    print(int(h_max + w_max))
else:
    print(int(h_max + w_max - 1))
i = list(map(int, input().split()))
if A > 10 or B > 10:
  print('1')
else:
  print('A * B')

### FIXED CODE ###

a = list(map(int,input().split()))
if a[0] >= 10 or a[1] >= 10:
  print('-1')
else:
  print(a[0] * a[1])
X, Y = map(int, input().split())

# dp = [[0 for _ in range(X+1)] for __ in range(Y+1)]
# dp[1][2] = 1
# dp[2][1] = 1

# for xi in range(X + 1):
#     for yi in range(Y + 1):
#         dp[xi][yi] = dp[xi - 1][yi - 2] + dp[xi - 2][yi - 1]

# print(dp[X][Y])

def help(x, y):
    if x < 0 or y < 0:
        return 0
    if (x == 1 and y == 2) or (x == 2 and y == 1):
        return 1
    else:
        return (help(x - 1, y - 2) + help(x - 2, y - 1))%(10e9+7)

print(help(X, Y))

### FIXED CODE ###

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

MD = pow(10, 9) + 7

def choose(n, a):
    x, y = 1, 1
    for i in range(a):
        x = x * (n - i) % MD
        y = y * (i + 1) % MD
    return x * pow(y, MD - 2, MD) % MD


a = (2*Y-X)//3
b = (Y-2*X)//-3

if a < 0 or b < 0 or (X+Y) % 3 != 0:
    print(0)
    import sys
    sys.exit()

print(choose(a+b, min(a,b)))
s = input()
 
count = 0
 
for i in s:
  if i == '1':
    count++
  
print(count)

### FIXED CODE ###

s = input()
 
count = 0
 
for i in s:
  if i == '1':
    count = count + 1
  
print(count)
#ALDS1_4-D Allocation
from collections import deque

def pIsAccptbl(w,k,p):
    tr = 0
    c = 0
    while(w):
        tmp = w.popleft()
        if( tr + tmp > p):
            tr = 0
            c += 1
        else:
            tr += tmp
    c+=1
    if c>k:return False
    else:return True
    
n,k = input().split()
w = []
w = deque()
for i in range(int(n)):
    w.append(int(input()))

p = max(w)

while(1):
    x=w.copy()
    if(pIsAccptbl(x,int(k),p)):
        print(p)
        break
    else:
        p+=1

### FIXED CODE ###

from collections import deque

def isPa(w,k,p):
    tr = 0
    c = 0
    d = deque(w)
    while(d):
        tmp = d.popleft()
        if(tmp > p):
            return False
        
        if( tr + tmp > p):
            tr = tmp
            c += 1
        else:
            tr += tmp
        if c+1>k:
            return False
    return True

def MaxInP(w,k,p):
    maxinp = 0
    tmp = 0
    d = deque(w)
    while(d):
        tmp += d.popleft();
        if(tmp > p):
            if(tmp > maxinp):
                maxinp = tmp
            tmp = 0
    return maxinp

n,k = [int(x) for x in input().split()]
w = deque()
for i in range(n):
    w.append(int(input()))
    
mean = int(sum(w)/k)
maxinp = MaxInP(w,k,mean)

if k == 1:
    print(mean)
else:
    minP = mean
    maxP = maxinp
    while(True):
        m = int ((minP + maxP)/2)
        if ( isPa(w,k,m) ):
            maxP = m
        else:
            minP = m
        if (minP+1 == maxP or minP == maxP):
            print(maxP)
            break
L,R = map(int,input().split())

ans = 0
min_mod = 2019

if R-L+1<2019 :
  if R % 2019 > 0:
    for i in range(L,R) :
      if L+1 == R :
        min_mod = (L*R) % 2019
      else :
        for j in range(L+1,R):
          if min_mod > (i*j) % 2019:
            min_mod = (i*j) % 2019

    ans = min_mod
    
print(ans)

### FIXED CODE ###

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

print(min(n*a,b))
x,y,z = map(int, input().split())
D=int x
T=int y
S=int z

if T-D/S>= 0:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

D,T,S = map(int, input().split())

if T-D/S >= 0:
    print("Yes")
else:
    print("No")
def triangle_check(a, b, c):
  if a>b+c:
    return False
  elif b>a+c:
    return False
  elif c>a+b:
    return False
  else:
    return True

def count_triangles(n, sticks):
  assert len(sticks) == n, "lenght of sticks does not match `n`"
  count = 0

  for i in range(len(sticks)):
    for j in range(i+1, len(sticks)):
      for k in range(j+1, len(sticks)):
        count += triangle_check(sticks[i], sticks[j] , sticks[k])

  return count




if __name__ == "__main__":

  n = int(input())
  sticks = list(set(map(int, input().split(" "))))
  num_triangles = count_triangles(n, sticks)
  print(num_triangles)

### FIXED CODE ###


def triangle_check(a, b, c):
  if a>b+c:
    return False
  elif b>a+c:
    return False
  elif c>a+b:
    return False
  else:
    return True

def count_triangles(n, sticks):
  assert len(sticks) == n, "lenght of sticks does not match `n`"
  count = 0

  for i in range(len(sticks)):
    for j in range(i+1, len(sticks)):
      for k in range(j+1, len(sticks)):
        count += triangle_check(sticks[i], sticks[j] , sticks[k])

  return count

def findnumberofTriangles(arr): 
  
    # Sort array and initialize count as 0 
    n = len(arr) 
    arr.sort() 
    count = 0
  
    # Fix the first element. We need to run till n-3 as 
    # the other two elements are selected from arr[i+1...n-1] 
    for i in range(0,n-2): 
  
        # Initialize index of the rightmost third element 
        k = i + 2
  
        # Fix the second element 
        for j in range(i+1,n): 
  
            # Find the rightmost element which is smaller 
            # than the sum of two fixed elements 
            # The important thing to note here is, we use 
            # the previous value of k. If value of arr[i] + 
            # arr[j-1] was greater than arr[k], then arr[i] + 
            # arr[j] must be greater than k, because the array 
            # is sorted. 
            while (k < n and arr[i] + arr[j] > arr[k]): 
                k += 1
  
            # Total number of possible triangles that can be 
            # formed with the two fixed elements is k - j - 1. 
            # The two fixed elements are arr[i] and arr[j]. All 
            # elements between arr[j+1] to arr[k-1] can form a 
            # triangle with arr[i] and arr[j]. One is subtracted 
            # from k because k is incremented one extra in above 
            # while loop. k will always be greater than j. If j 
            # becomes equal to k, then above loop will increment k, 
            # because arr[k] + arr[i] is always greater than arr[k] 
            if(k>j): 
                count += k - j - 1
  
    return count 

if __name__ == "__main__":

  n = int(input())
  sticks = sorted(list(map(int, input().split(" "))))
  # num_triangles = count_triangles(n, sticks)
  num_triangles = findnumberofTriangles(sticks)
  print(num_triangles)
import math

A, B, K = map(int, input().split())
gcd = math.gcd(A, B)
l = []

for i in range(1, gcd+1):
  if gcd % i == 0:
    l.append(i)
  else:
    pass
l.reverse()
print(l[K-1])

### FIXED CODE ###

from fractions import gcd

A, B, K = map(int, input().split())
gcd = gcd(A, B)
l = []

for i in range(1, gcd+1):
  if gcd % i == 0:
    l.append(i)
  else:
    pass
l.reverse()
print(l[K-1])
#!/usr/bin/env python3

n = int(input())
a = list(map(int,input().split()))
cnt = [0]*(10**5)
for i in a:
    cnt[i] += 1
cnt.sort()
#print(cnt[-1])
if cnt[-1] >= (n+1)//2: print(n//2 - cnt[-2])
else: print((n+1)//2 - cnt[-1]+ n//2 - cnt[-2])

### FIXED CODE ###

#!/usr/bin/env python3

n = int(input())
a = list(map(int,input().split()))
cnt_odd = [0]*(10**5+1)# a[2k]での個数
cnt_even = [0]*(10**5+1)
for i in range(n):
    if i  %2: cnt_odd[a[i]] += 1
    else: cnt_even[a[i]] += 1
odd,idx_odd=zip(*sorted(zip(cnt_odd,list(range(10**5+1)))))
even,idx_even=zip(*sorted(zip(cnt_even,list(range(10**5+1)))))
#print(odd[-1],even[-2],odd[-2],even[-1])
if idx_even[-1]!=idx_odd[-1]:
    print(n - odd[-1] - even[-1])
else:
    print(n - max(odd[-1]+even[-2],odd[-2]+even[-1]))
#ちゃんとテストケース書かないと落ちる