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

from collections import defaultdict
from bisect import bisect
from sys import stdin


def main():
    input = lambda: stdin.readline()[:-1]
    N = int(input())
    S = input()

    rgb = defaultdict(list)
    for i, s in enumerate(S):
        rgb[s].append(i)

    def count_(s1, s2):
        ret = 0
        x = bisect(rgb[s1], i)
        for j in rgb[s1][x:]:
            y = bisect(rgb[s2], j)
            d = j - i
            if j + d < N and S[j+d] == s2:
                ret += len_[s2] - y - 1
            else:
                ret += len_[s2] - y
        return ret

    ans = 0
    len_ = {'R': len(rgb['R']), 'G': len(rgb['G']), 'B': len(rgb['B'])}
    for i, s in enumerate(S):
        if s == 'R':
            for s1, s2 in (('G', 'B'), ('B', 'G')):
                ans += count_(s1, s2)
        elif s == 'G':
            for s1, s2 in (('R', 'B'), ('B', 'R')):
                ans += count_(s1, s2)
        else:
            for s1, s2 in (('R', 'G'), ('G', 'R')):
                ans += count_(s1, s2)
    print(ans)


main()


### FIXED CODE ###

from bisect import bisect
from sys import stdin


def main():
    input = lambda: stdin.readline()[:-1]
    N = int(input())
    S = input()

    rgb = {'R': [], 'G': [], 'B': []}
    for i, s in enumerate(S):
        rgb[s].append(i)

    def count_(s1, s2):
        ret = 0
        x = bisect(rgb[s1], i)
        for j in rgb[s1][x:]:
            y = bisect(rgb[s2], j)
            d = j - i
            if j + d < N and S[j+d] == s2:
                ret += len_[s2] - y - 1
            else:
                ret += len_[s2] - y
        return ret

    ans = 0
    len_ = {'R': len(rgb['R']), 'G': len(rgb['G']), 'B': len(rgb['B'])}
    for i, s in enumerate(S):
        if s == 'R':
            for s1, s2 in (('G', 'B'), ('B', 'G')):
                ans += count_(s1, s2)
        elif s == 'G':
            for s1, s2 in (('R', 'B'), ('B', 'R')):
                ans += count_(s1, s2)
        else:
            for s1, s2 in (('R', 'G'), ('G', 'R')):
                ans += count_(s1, s2)
    print(ans)


main()
### BUGGY CODE ###

from collections import Counter
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    lis = list(map(int,input().split()))
    ans = Counter(lis)
    for j in range(n):
        ans[lis[j]] -= 1
        su = 0
        for k in ans.values():
            su += (k - 1) * k // 2
        print(su)
        ans[lis[j]] += 1

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import Counter
import sys
input = sys.stdin.buffer.readline

def main():
    n = int(input())
    lis = list(map(int,input().split()))
    d = Counter(lis)
    su = 0
    for e in d:
        su += (d[e] - 1) * d[e] // 2

    for e in lis:
        if d[e] <= 1:
            print(su)
        else:
            k = d[e]
            res = su - k*(k-1)//2 + (k-1)*(k-2)//2
            print(res)

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

n = int(input())
s = input()
cnt = 0
for i in range(n-3):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            if j-i == k-j: continue
            if s[i] != s[j]:
                if s[j] != s[k]:
                    if s[i] != s[k]:
                        cnt += 1
print(cnt)


### FIXED CODE ###

n = int(input())
s = input()
cnt = s.count("R") * s.count("G") * s.count("B")
for i in range(n-2):
    pl = 1
    while i + pl * 2 < n:
        if s[i] != s[i+pl] and s[i+pl] != s[i+pl*2] and s[i] != s[i+pl*2]:
            cnt -= 1
        pl += 1
print(cnt)
### BUGGY CODE ###

n,m = map(int,input().split())

max = m//n

if m%n == 0:
    print(max)
else:
    for i in range(max):
        if m%(max-i) == 0:
            print(max-i)
            break





### FIXED CODE ###

n,m = map(int,input().split())

max = m//n
lis = []


for i in range(int(m**0.5)):
    if i != 0 and m%i == 0:
        lis.append(i)
l = len(lis)
for i in range(l):
    if m/lis[i] != lis[i]:
        lis.append(m//lis[i])

lis.sort()
lis = lis[::-1]

if m%n == 0:
    print(max)
else:
    for line in lis:
        if line > max:
            continue
        else:
            if m/line > n:
                print(line)
                break
### BUGGY CODE ###

import math
n=int(input())
a=sorted(list(map(int,input().split())),reverse=True)
maxcomb=0
ans=[0,0]

def combination(n,r):
    return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))

for i in range(n-1):
    for j in range(i+1,n):
        comb=combination(a[i], a[j])
        if(maxcomb < comb):
            maxcomb = comb
            ans=[a[i],a[j]]
print(str(ans[0])+" "+str(ans[1]))

### FIXED CODE ###

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

def mid(a):
    if(a%2!=0):
        return (a+1)//2
    else:
        return a//2

ai=a[0]
temp=list(map(lambda x:abs(x-mid(ai)),a[1:]))
bi=a[temp.index(min(temp))+1]
print(str(ai)+" "+str(bi))
### BUGGY CODE ###

# ソートすりゃいい てっぺんは小さい方から、あとは大きい方から比較していって、ダメになったら抜ける
n = int(input())
A = list(sorted(list(map(int, input().split()))))
B = list(sorted(list(map(int, input().split()))))
C = list(sorted(list(map(int, input().split()))))

count = 0
for a in A:
    for b in B[::-1]:
        if a >= b:
            break
        for c in C[::-1]:
            if b >= c:
                break
            count += 1
print(count)


### FIXED CODE ###

# それぞれソート済みとして, 整数でAi<BjかつBj<Ckとなるjを求める(にぶたん)

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


def lower_bound(arr, target):
    # targetを超える最小の値のインデックス
    if target > arr[-1]:
        return None
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] > target:
            right = mid
        else:
            left = mid + 1
    return right


def upper_bound(arr, target):
    # target以上の最小の値のインデックス
    if target < arr[0]:
        return None
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] >= target:
            right = mid
        else:
            left = mid + 1
    return right


count = 0

for b in B:
    ai = upper_bound(A, b)
    ci = lower_bound(C, b)
    if ai is not None and ci is not None:
        count += ai * (N - ci)

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

from collections import defaultdict
N = int(input())
S = str(input())
d = defaultdict(list)
ans = 0
cnt = 0
for i in range(N):
    d[S[i]].append(i)
for x in ("abcdefghijklmnopqrstuvwxyz"):
    for i in range(len(d[x])):
        for j in range(i+1, len(d[x])):
            while S[d[x][i] + cnt] == S[d[x][j] + cnt] and d[x][i] + cnt < d[x][j]:
                cnt += 1
                if d[x][j] + cnt >= len(S):
                    break
            ans = max(cnt,ans)
            cnt = 0
print(ans)



### FIXED CODE ###

N = int(input())
S = str(input())
dp = [[0 for i in range(N+1)] for i in range(N+1)]

for i in reversed(range(N)):
    for j in reversed(range(N)):
        if S[i] == S[j]:
            dp[i][j] = dp[i+1][j+1] + 1
ans = 0
for i in range(N):
    for j in range(N):
        if j > i:
            tmp = min(j-i,dp[i][j])
            ans = max(tmp,ans)
print(ans)
### BUGGY CODE ###

import heapq

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

heapq.heapify(a)

for i in range(m):
    b,c=map(int, input().split())
    for g in range(b):
        _min = heapq.heappop(a)
        if _min<c:
            heapq.heappush(a,c)
        else:
            heapq.heappush(a,_min)
            break
print(sum(a))

### FIXED CODE ###

import heapq

n,m = map(int, input().split())
a = list(map(int, input().split()))
bc = [[int(i) for i in input().split()] for i in range(m)]
bc.sort(key=lambda x: x[1],reverse=True)

heapq.heapify(a)

for i in range(m):
    b,c=bc[i]
    for g in range(b):
        _min = heapq.heappop(a)
        if _min<c:
            heapq.heappush(a,c)
        else:
            heapq.heappush(a,_min)
            break
print(sum(a))
### BUGGY CODE ###

# C - Sum of gcd of Tuples (Easy)
import math

k = int(input())
s = 0

for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            s += math.gcd(a,math.gcd(b,c))

print(s)


### FIXED CODE ###

# C - Sum of gcd of Tuples (Easy)

import math

k = int(input())
s = 0
for a in range(1,k+1):
    for b in range(1,k+1):
        gcdab = math.gcd(a,b)
        if  gcdab== 1:
            s += k
        else:
            for c in range(1,k+1):
                s += math.gcd(gcdab,c)

print(s)
### BUGGY CODE ###

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

counter = 0
for i in range(len(A)):
    warikire = False
    for j in range(len(A)):
        # print(i, j, A[i], A[j])
        if i == j:
            continue
        if A[i] % A[j] == 0:
            warikire = True
            break
        if A[i] < A[j]:
            break
    counter += 1 if not warikire else 0
print(counter)

### FIXED CODE ###

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

max_number = max(A) + 1
ng = [False] * max_number
counter = 0
prev = 0
for ai in A:
    if ai == prev:
        counter -= 1
        prev = 0
    if not ng[ai]:
        counter += 1
        prev = ai
    for i in range(ai, max_number, ai):
        ng[i] = True
print(counter)
### BUGGY CODE ###

N = int(input())
stn = input()
m = stn.count('R')

for i in range(N+1):
    white_l = stn.count('W', 0, i)
    red_r = stn.count('R', i, N)
    if red_r >= white_l:
        m = min(m, red_r)
    else:
        m = min(m, white_l)

print(m)

### FIXED CODE ###

N = int(input())
stn = input()
m = stn.count('R')
r = m
w = 0
for i in range(N):
    if stn[i]=='R':
        r -= 1
    else:
        w += 1

    m = min(m, max(r,w))

print(m)
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
init = (10 ** 4) * N
dp = [init] * N
dp[0] = 0

for i in range(1, N):
    min = init
    for j in range(1, K+1):
        if i - j < 0:
            break
        tmp = dp[i-j] + abs(h[i] - h[i-j])
        if tmp < min:
            min = tmp
    dp[i] = min

print(dp[N-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
h = [int(x) for x in input().split()]
dp = [0] * N

for i, hi in enumerate(h):
    if i == 0:
        continue
    if i - K < 0:
        dp[i] = min(dpk + abs(hi-hk) for dpk, hk in zip(dp[:i], h[:i]))
    else:
        dp[i] = min(dpk + abs(hi-hk) for dpk, hk in zip(dp[i-K:i], h[i-K:i]))

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

(n,q),*t=[map(int,t.split())for t in open(0)]
s=[0]
d=s*n
f=s+[1]*n
e=[[]for _ in d]
for a,b in t:
 if~-n:n-=1;e[a-1]+=b-1,;e[b-1]+=a-1,
 else:d[a-1]+=b
while s:
 v=s.pop()
 for w in e[v]:
  if f[w]:d[w]+=d[v];s+=w,;f[w]=0
print(*d)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
def dfs(v):
    for w in e[v]:
        if root[w]>=0:continue
        root[w]=v
        dfs(w)
def dfs2(v):
    for w in e[v]:
        if f[w]:continue
        f[w]=1
        data[w]+=data[v]
        dfs2(w)
input=sys.stdin.readline
n,q=map(int,input().split())
e=[[]for _ in range(n)]
root=[0]+[-1]*(n-1)
data=[0]*n
for _ in range(n-1):
    a,b=map(int,input().split())
    e[a-1]+=b-1,
    e[b-1]+=a-1,
#dfs(0)
for _ in range(q):
    p,x=map(int,input().split())
    data[p-1]+=x
f=[1]+[0]*(n-1)
dfs2(0)
print(*data)
### BUGGY CODE ###

from collections import defaultdict
N, K = map(int, input().split())
AB = [[int(i) for i in input().split()] for _ in range(N)]

visited = defaultdict(lambda : False)
L = set()
def dfs(x) :
    if visited[x] :
        return 
        
    visited[x] = True
    for i in range(30) :
        if x & (1 << i) == 0 :
            continue
            
        y = x ^ (1 << i)
        if y <= K :
            L.add(y)
        else :
            dfs(y)


dfs((1 << (len(bin(K)) - 2)) - 1)
L.add(K)

ret = 0
for mask in L :
    s = 0
    for A, B in AB :
        if A & ~mask == 0 :
            s += B
    ret = max(ret, s)
    
print(ret)

### FIXED CODE ###

N, K = map(int, input().split())
AB = [[int(i) for i in input().split()] for _ in range(N)]

ret = 0
for A, B in AB :
    if A & ~K == 0 :
        ret += B
        
for i in range(30) :
    if K & (1 << i) == 0 :
        continue
        
    k = K
    k ^= 1 << i
    k |= (1 << i) - 1
    s = 0
    for A, B in AB :
        if A & ~k == 0 :
            s += B
            
    ret = max(ret, s)
    
print(ret)
### BUGGY CODE ###

import sys 
sys.setrecursionlimit(10**6)

n, q = map(int, input().split())
G = [[] for _ in range(n)]
point = [0]*n
for _ in range(n-1):
    a,b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
for i in range(q):
    p, x = map(int, input().split())
    p = p-1
    point[p] += x

def dfs(now, prev = -1):
    for next in G[now]:
        if next == prev:
            continue
        point[next] += point[now]
        dfs(next, now)

dfs(0)
print(*point)    
 


### FIXED CODE ###

import sys 
sys.setrecursionlimit(10**6)
import sys
def input():
    return sys.stdin.readline()[:-1]
n, q = map(int, input().split())
G = [[] for _ in range(n)]
point = [0]*n
for _ in range(n-1):
    a,b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
for i in range(q):
    p, x = map(int, input().split())
    p = p-1
    point[p] += x

def dfs(now, prev = -1):
    for next in G[now]:
        if next == prev:
            continue
        point[next] += point[now]
        dfs(next, now)

dfs(0)
print(*point)
### BUGGY CODE ###

A, B, N = map(int, input().split())
ans = 0
for x in range(int(N**0.5), N+1):
    ans  = max(ans, (A*x)//B-A*(x//B))
print(ans)

### FIXED CODE ###

A, B, N = map(int, input().split())
ans = 0
x = min(B-1, N)
print((A*x)//B-A*(x//B))
### BUGGY CODE ###

import numpy as np

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

cmod = np.zeros( 2019 )
cmod[ 0 ] += int( 1 )

tkm1 = int( 0 )
for km in range( n ):
    k = n - km
    tkm1 = tkm1 + 10**( n - k ) * int( ss[ k - 1 ] )
    lmod = tkm1 % 2019
    cmod[ lmod ] += 1
#    print( lmod, tkm1 )

ans = int( 0 )
for icmod in cmod:
    ans += icmod * ( icmod-1 ) * 0.5e0

ans = int( ans )
print( ans )


### FIXED CODE ###

import numpy as np

s = input()

d = [ int( 0 ) ] * 2019
d[ 0 ] = int( 1 )
r = int( 0 )
t = int( 1 )

for si in reversed( s ):
#    print( si )

    r = int( si ) * t + r
    r = r % 2019

    t = t * 10
    t = t % 2019

    d[ r ] = d[ r ] + 1

ans = int( 0 )
for di in d:
    ans = ans + di * ( di - 1 ) // 2

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

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

n = 100
D = [0]*(n+2)

for i in range(N):
    s = list(bin(A[i])[2:])[::-1]
    for j in range(len(s)):
        D[j] += int(s[j])
ans = 0
for i in range(n):
    ans += D[i]*(N-D[i])*2**i
    ans %= 10**9+7
print(ans)


### FIXED CODE ###

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

n = 62
D = [0]*n

for i in range(N):
    s = list(bin(A[i])[2:])[::-1]
    s = [i for i in range(len(s)) if s[i]=='1']
    for j in s:
        D[j] += 1
ans = 0
for i in range(n):
    ans += D[i]*(N-D[i])*2**i
    ans %= 10**9+7
print(ans)
### BUGGY CODE ###

N = int(input())
def divisor_list(num):
  ans = []
  for i in range(1, int(num**0.5)+1):
    if num % i == 0:
      ans.append(i)
      if i != num // i:
        ans.append(num//i)
  return ans
d_list = sorted(divisor_list(N))
ans = 10**12
for i in d_list:
  for j in d_list:
    if i*j == N and ans > i+j-2:
      ans = i+j-2
print(ans)

### FIXED CODE ###

N = int(input())
def divisor_list(num):
  ans = []
  for i in range(1, int(num**0.5)+1):
    if num % i == 0:
      ans.append(i)
      if i != num // i:
        ans.append(num//i)
  return ans
d_list = sorted(divisor_list(N))
ans = 10**12
for i in d_list:
    if ans > i+N//i-2:
      ans = i+N//i-2
print(ans)
### BUGGY CODE ###

from collections import deque


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    d = [[-1 for _ in range(W)] for _ in range(H)]

    q = deque([])
    q.appendleft((0, Ch - 1, Cw - 1))

    while len(q):
        worp_count, x, y = q.popleft()

        if d[x][y] != -1:
            continue
        d[x][y] = worp_count

        for i, j in ((a, b) for a in range(-2, 3) for b in range(-2, 3)):
            nx = x + i
            ny = y + j
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                if i == 0 and j == 0:
                    continue
                elif abs(i) + abs(j) == 1:
                    q.appendleft((worp_count, nx, ny))
                else:
                    q.append((worp_count + 1, nx, ny))

    print(d[Dh - 1][Dw - 1])


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    d = [[-1 for _ in range(W)] for _ in range(H)]

    q = deque([])
    q.appendleft((0, Ch - 1, Cw - 1))

    while len(q):
        worp_count, x, y = q.popleft()

        if d[x][y] != -1:
            continue
        d[x][y] = worp_count

        for i, j in ((a, b) for a in range(-2, 3) for b in range(-2, 3)):
            nx = x + i
            ny = y + j
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                if i == 0 and j == 0:
                    continue
                elif abs(i) + abs(j) == 1:
                    q.appendleft((worp_count, nx, ny))
                else:
                    q.append((worp_count + 1, nx, ny))

    print(d[Dh - 1][Dw - 1])


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

# -*- coding: utf-8 -*-
import math
Q = int(input())

ls = []
rs = []
for n in range(Q):
    l, r = map(int, input().split())
    ls.append(l)
    rs.append(r)
    num = 0

max_r = max(rs)

def eratos(n):
    if n == 1:
        return set()
    primes = [1 for i in range(n+1)]
    primes[0] = 0
    primes[1] = 0
    for i in range(2,math.floor(math.sqrt(n))+1):
        if primes[i] == 1:
            j = i + i
            while j <= n:
                primes[j] = 0
                j = j + i
    return primes


def count_similar(era, n):
    is_similar = [0 for i in range(n+1)]
    for i in range(n+1):
        if era[i] == 1 and era[int((i+1)/2)] == 1:
            is_similar[i] = 1
    count_similar = [0 for i in range(n+1)]
    for i in range(n+1):
        count_similar[i] = sum(is_similar[0:i+1])
    return count_similar




era = eratos(max_r)
cnt = count_similar(era, max_r)

for l, r in zip(ls, rs):
    print(cnt[r] - cnt[l-1])



### FIXED CODE ###

# -*- coding: utf-8 -*-
import math
Q = int(input())

ls = []
rs = []
for n in range(Q):
    l, r = map(int, input().split())
    ls.append(l)
    rs.append(r)
    num = 0

max_r = max(rs)

def eratos(n):
    if n == 1:
        return set()
    primes = [1 for i in range(n+1)]
    primes[0] = 0
    primes[1] = 0
    for i in range(2,math.floor(math.sqrt(n))+1):
        if primes[i] == 1:
            j = i + i
            while j <= n:
                primes[j] = 0
                j = j + i
    return primes


def count_similar(era, n):
    count_similar = [0 for i in range(n+1)]
    for i in range(1,n+1):
        count_similar[i] = count_similar[i-1]
        if era[i] == 1 and era[int((i+1)/2)] == 1:
            count_similar[i] += 1
    return count_similar




era = eratos(max_r)
cnt = count_similar(era, max_r)

for l, r in zip(ls, rs):
    print(cnt[r] - cnt[l-1])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
INF = 10**9
ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        ans += A[i] ^ A[j]

ans = ans % (INF + 7)
print(ans)

### FIXED CODE ###

import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
ans = 0
mod = 10 ** 9 + 7

for i in range(60):
    x, y = 0, 0    
    B = A >> i & 1
    x = np.count_nonzero(B)
#     for Ai in A:
#         if Ai >> i & 1:
#             x += 1
    y = N - x
    ans += (x * y) * (2 ** i)
    
print(ans%mod)
### BUGGY CODE ###

import math

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

def shellSort(A,n):
	cnt = 0
	#m = n//2 + 1
	#G = [2*i + 1*(i==0) for i in range(m)[::-1]]
	m = int(math.log(n,2)) + 1
	G = [2**i for i in range(m)[::-1]]
	for g in G:
		A,cnt = insertionSort(A,n,g,cnt)
	return A,m,G,cnt

if __name__ == '__main__':
	
	n = int(input())
	A = []
	[A.append(int(input())) for i in range(n)]
	
	'''
	data = [int(d) for d in data.split('\n')]
	n = data.pop(0)
	A = data[:]
	'''
	
	A,m,G,cnt = shellSort(A,n)
	print(m)
	print(' '.join([str(i) for i in G]))
	print(cnt)
	[print(a) for a in A]

### FIXED CODE ###

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

def shellSort(A,n):
	cnt = 0
	G = [1]
	while G[-1]*3+1 <= n:
		G.append(G[-1]*3 + 1)
	G = G[::-1]
	m = len(G)
	for g in G:
		A,cnt = insertionSort(A,n,g,cnt)
	return A,m,G,cnt

if __name__ == '__main__':
	
	n = int(input())
	A = []
	[A.append(int(input())) for i in range(n)]
	
	'''
	data = [int(d) for d in data.split('\n')]
	n = data.pop(0)
	A = data[:]
	'''
	
	A,m,G,cnt = shellSort(A,n)
	print(m)
	print(' '.join([str(i) for i in G]))
	print(cnt)
	[print(a) for a in A]
### BUGGY CODE ###

K = int(input())


def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)


ans = 0
for a in range(K):
    for b in range(K):
        for c in range(K):
            ans += gcd(gcd(a+1, b+1), c+1)

print(ans)


### FIXED CODE ###

K = int(input())


def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)


ans = 0
for a in range(K):
    for b in range(K):
        for c in range(K):
            ans += gcd(gcd(a+1, b+1), c+1)

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

N = int(input())
S = input()

ans = 0
left, right = 0, 1

while right < N:
    s = S[left:right]
    if s in S[right:]:
        right += 1
        ans = max(ans, len(s))
    else:
        left = right - 1

print(ans)


### FIXED CODE ###

N = int(input())
S = input()

ans = 0
left, right = 0, 1
while right < N:
    s = S[left:right]
    if s in S[right:]:
        ans = max(ans, len(s))
        right += 1
    else:
        left += 1

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

from bisect import bisect_left, bisect_right
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i, a in enumerate(L):
    for j, b in enumerate(L[i+1:]):
        l = abs(a - b)
        r = a + b
        top = bisect_left(L[i+j+2:], r)
        bot = bisect_right(L[i+j+2:], l)
        ans += top - bot
print(ans)


### FIXED CODE ###

from bisect import bisect_left, bisect_right
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(N-1, 1, -1):
    for j in range(i - 1, 0, -1):
        x = L[i] - L[j]
        bottom = bisect_right(L, x)
        if j > bottom:
            ans += j - bottom
print(ans)
### BUGGY CODE ###

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

for i in range(1, N+1):
  for j in range(1, i+1):
    if A[j-1] < A[i-1]:
      count += 1
      break

ans = N - count
print(ans)

### FIXED CODE ###

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

M = N+1
ans = 0

for i in range(1, N+1):
  if M > A[i-1]:
    M = A[i-1]
    ans += 1

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

N=int(input())
for i in range(1,3501):
    for j in range(1,3501):
        aw=(N*i*j)
        bw=4*i*j-N*i-N*j
        if bw<=0:
            continue
        elif aw%bw==0:
            print(i,j,int(aw/bw))
            break

### FIXED CODE ###

N=int(input())
for i in range(1,3501):
    for j in range(1,3501):
        bw=4*i*j-N*i-N*j
        if bw<=0:
            continue
        if (N*i*j)%bw==0:
            print(i,j,(N*i*j)//bw)
            exit()