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

import itertools
Q = int(input())
l, r = [0]*Q, [0]*Q
for i in range(Q):
    l[i], r[i] = map(int, input().split())
lr = zip(l,r)

def Is_prime(n):
    # nが1以下ならFalse
    if n<=1:
        return False
    # nが2または3ならTrue
    if n==2 or n==3:
        return True
    # nが2の倍数ならFalse
    if n%2==0:
        return False
    # nの平方根を整数で取得
    sqrt_root = int(n**.5)
    # nがnの平方根以下の3以上の奇数で1回でも割れたらFalse
    for i in range(3,sqrt_root+1,2):
        if n%i==0:
            return False
    # 上の条件を全てぬけたものはTrue
    return True

def Prime_table(n):
    res = []
    for i in range(n+1):
        if Is_prime(i):
            res.append(i)
    return res

ptb = Prime_table(max(r)+1)
def is_like(x):
    if x in ptb and (x+1)//2 in ptb:
        return 1
    return 0

L = list(itertools.accumulate(list(map(is_like,range(max(r)+1)))))

for l,r in lr:
    print(L[r]-L[l-1])


### FIXED CODE ###

MAX = 101010
is_prime = [1]*MAX
is_prime[0] = 0
is_prime[1] = 0
for i in range(2,MAX):
    if not is_prime:
        continue
    for j in range(i*2,MAX,i):
        is_prime[j] = 0

a = [0]*MAX
for i in range(MAX):
    if i%2==0:
        continue
    if is_prime[i] and is_prime[(i+1)//2]:
        a[i] = 1


s = [0]*(MAX+1)
for i in range(MAX):
    s[i+1] = s[i] + a[i]

Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(s[r+1]-s[l])
### BUGGY CODE ###

import fractions
from functools import reduce

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

for i in range(n):
    b = a[:i]+a[i+1:]
    ans = max(reduce(fractions.gcd, b), ans)

print(ans)

### FIXED CODE ###

import fractions

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

l_gcd = [0]
for i in range(n):
    l_gcd.append(fractions.gcd(l_gcd[-1], a[i]))
# print(l_gcd)

r_gcd = [0]
for i in range(n):
    r_gcd.append(fractions.gcd(r_gcd[-1], a[-(i+1)]))
r_gcd.reverse()
# print(r_gcd)

for i in range(n):
    ans = max(ans, fractions.gcd(l_gcd[i], r_gcd[i+1]))
print(ans)
### BUGGY CODE ###

from functools import reduce
from fractions import gcd

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
mod = 10**9 + 7
n = int(input())
As = list(map(int, input().split()))

lcm = lcm_list(As)
ans = 0
for i in range(n):
    ans += lcm // As[i]
    ans %= mod

print(ans)

### FIXED CODE ###

from functools import reduce
from fractions import gcd

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers)
mod = 10**9 + 7
n = int(input())
As = list(map(int, input().split()))

lcm = lcm_list(As)
b = [lcm//As[i] for i in range(n)]

print(sum(b) % mod)
### BUGGY CODE ###

import numpy as np
inp1 = input().split()
inp2 = input().split()

a = int(inp1[0])
b = np.array(inp2).astype(int)
ansno = a
maxno = b[0]

for ii,i in enumerate(b):
  bslice = b[:ii+1]
  minb = np.min(bslice)
  if minb != i:
    ansno -=1
  
print(ansno)

### FIXED CODE ###

n = int(input())
m = input().split()
ppp = list(map(int, m))
max = 2*10**5+1
ans = 0
for p in ppp:
    if p < max:
        ans += 1
        max = p
print(ans)
### BUGGY CODE ###

A,B,N=list(map(int,input().split()))
list_ans=[]
minimum=min(N-10,0)
for i in range(minimum,N+1):
  list_ans.append(int(A*i/B)-A*int(i/B))
print(int(max(list_ans)))

### FIXED CODE ###

A,B,N=list(map(int,input().split()))
list_ans=[]
minimum=min(B-1,N)
print(int(A*minimum/B)-A*int(minimum/B))
### BUGGY CODE ###

N=int(input())
S=[input() for i in range(N)]
S.sort()
def list_count(my_list):
    dic={} #辞書型の宣言
    for num in my_list:
        if num in dic: #もしnumがkeyとして辞書にあれば
            dic[num]+=1 #valueに+1
        else: #なければ
            dic[num]=1 #dicにnumというkeyを追加し、対応するvalueを1とする
    return dic

A=list_count(S)
max_k_list = [kv[0] for kv in A.items() if kv[1] == max(A.values())]
max_k_list.sort()
for j in range(len(max_k_list)):
    print(max_k_list[j])

### FIXED CODE ###

N=int(input())
S=[input() for i in range(N)]
S.sort()
def list_count(my_list):
    dic={} #辞書型の宣言
    for num in my_list:
        if num in dic: #もしnumがkeyとして辞書にあれば
            dic[num]+=1 #valueに+1
        else: #なければ
            dic[num]=1 #dicにnumというkeyを追加し、対応するvalueを1とする
    return dic
K=[]
A=list_count(S)
ookii=max(A.values())
K.append(ookii)
max_k_list = [kv[0] for kv in A.items() if kv[1] == K[0]]
max_k_list.sort()
for j in range(len(max_k_list)):
    print(max_k_list[j])
### BUGGY CODE ###

N, K = map(int, input().split())
As = list(map(int, input().split()))
S = []
for i in range(N):
  a = As[i]
  try:
    j = As.index(a, i+1)+1
    S.append((j//N, j%N))
  except:
    j = As.index(a)+1
    S.append((1+j//N, j%N))
#print(S)
count = 0
p = 0
while True:
  c, p = S[p]
  count += c
  if p == 0:
    break
#print(count)
K = K%count
#print(K)
s = []
for k in range(K):
  for a in As:
    i = -1
    for j in range(len(s)):
      if s[j] == a:
        i = j
    if i < 0:
      s.append(a)
    else:
      s = s[0:i]
print(" ".join(map(str, s)))


### FIXED CODE ###

N, K = map(int, input().split())
As = list(map(int, input().split()))
M = [[] for i in range(200001)]
for i, a in enumerate(As):
  M[a].append(i)
S = []
for i, a in enumerate(As):
  l = M[a]
  index = l.index(i)
  if index+1 == len(l):
    n = l[0]+N
  else:
    n = l[index+1]
  S.append(n+1-i)
#print(S)
p = 0
while True:
  p = p+S[p%N]
  if p%N == 0:
    break
count = p//N
#print(count)
K = K%count
#print(K)
p = 0
s = []
while p < N*K:
  q = p+S[p%N]
  if q > N*K:
    s.append(As[p%N])
    p = p+1
  else:
    p = q
print(" ".join(map(str, s)))
### BUGGY CODE ###

from scipy.misc import comb
from collections import defaultdict
d = defaultdict(lambda: -1)
d_ = defaultdict(lambda: -1)
n = int(input())
a = [int(x) for x in input().split()]

for i in range(len(a)):
  a_ = a.copy()
  b = a_.pop(i)
  if d[str(b)] != -1:
    print(d[str(b)])
    continue
  A = list(set(a_))
  ans = 0
  for j in A:
    c = a_.count(j)
    if d_[str(c)] != -1:
      ans += d_[str(c)]
    else:
      e = comb(c, 2, exact=True)
      ans += e
      d_[str(c)] = e

  d[str(b)] = ans
  print(ans)




### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split()]
from collections import defaultdict
d = defaultdict(int)
for i in a:
  d[i] += 1

total = 0
for i in set(a):
  x = d[i]
  total += x*(x-1)/2

for i in a:
  x = d[i]
  print(int(total-((x*(x-1)/2))+((x-1)*(x-2)/2)))
### BUGGY CODE ###

n, k = map(int,input().split())
li = list(map(int,input().split()))

f_inf = float('inf')
dp = [f_inf]*(10**5+10)

# 初期値
dp[0] = 0
for i in range(1,n):
    for j in range(1,k+1):
        if (i-j>=0):
            dp[i] = min(dp[i],dp[i-j]+abs(li[i]-li[i-j]))
print(dp[n-1])

### FIXED CODE ###

n, k = map(int,input().split())
li = list(map(int,input().split()))

f_inf = float('inf')
dp = [f_inf]*(10**5+10)

# 初期値
dp[0] = 0
for i in range(1,n):
    for j in range(1,k+1):
        if (i-j>=0):
            dp[i] = min(dp[i],dp[i-j]+abs(li[i]-li[i-j]))
print(dp[n-1])
### BUGGY CODE ###

S = input()
Q = int(input())
hanten = 0
for i in range(Q):
    query = list(input().split())
    if query[0] == '1':
        hanten +=1
    else:
        if query[1] == '1':
            if hanten % 2 == 0:
                S = query[2] + S
            else:
                S = S + query[2]
        else:
            if hanten % 2 == 1:
                S = query[2] + S
            else:
                S = S + query[2]
if hanten % 2 == 0:
    print(S)
else:
    print(S[::-1])

### FIXED CODE ###

S = input()
Q = int(input())
bs = ''
fs = ''
hanten = 0
for i in range(Q):
    query = list(input().split())
    if query[0] == '1':
        hanten += 1
    else:
        if query[1] == '1':
            if hanten % 2 == 0:
                fs += query[2]
            else:
                bs += query[2]
        else:
            if hanten % 2 == 0:
                bs += query[2]
            else:
                fs += query[2]
if hanten % 2 == 0:
    print(fs[::-1]+S+bs)
else:
    print(bs[::-1]+S[::-1]+fs)
### BUGGY CODE ###

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

flag = False

yki = min(n,y//10000)
for i in range(yki+1):
    for j in range(y-i+1):
        nogu = n -i - j
        if nogu*1000 + i*10000 + j*5000 == y and nogu >= 0:
            ans = [i,j,nogu]
            flag = True
            break
    if flag:
        break

if flag:
    print(*ans,sep = " ")
else:
    print(-1,-1,-1)

### FIXED CODE ###

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

flag = False

yki = min(n,y//10000)
for i in range(yki+1):
    for j in range(n-i+1):
        nogu = n -i - j
        if nogu*1000 + i*10000 + j*5000 == y and nogu >= 0:
            ans = [i,j,nogu]
            flag = True
            break
    if flag:
        break

if flag:
    print(*ans,sep = " ")
else:
    print(-1,-1,-1)
### BUGGY CODE ###

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

AB = [x for x in range(A, B+1)]

ans = 0
for ab in AB:
    ans = ans ^ ab

print(ans)







### FIXED CODE ###

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

def cal_xor(X):
    X = X+1
    xor_sum = 0
    digit = 1
    while digit < X:
        digit *= 2
        bit_count = (X // digit) * (digit // 2)
        bit_count += max(0, (X % digit) - (digit // 2))
        
        if bit_count % 2 == 1:
            xor_sum += digit // 2
    
    return xor_sum
        

ans = cal_xor(A-1) ^ cal_xor(B)
print(ans)
### BUGGY CODE ###

def main():
    import sys
    input=sys.stdin.readline
    s=input()
    alpha="abcdefghijklmnopqrstuvwxyz"
    #s=alpha*8000
    #s="a"*200000
    l=len(s)
    alpha2={j:i for i,j in enumerate(alpha)}
    memo=[[0]*26 for _ in range(l,-1,-1)]
    for i in range(26):
        memo[l][i]=l+1
    for x,y in alpha2.items():
        for i in range(l-1,-1,-1):
            if s[i]==x:
                memo[i][y]=i+1
            else:
                memo[i][y]=memo[i+1][y]
    def search(n,seq):
        temp=-1
        for i in range(26):
            if memo[n][i]>temp:
                temp=memo[n][i]
        return temp,seq+1
    n,seq=0,0
    while n<=l:
        n,seq=search(n,seq)
    ans_len=seq
    ans=""
    temp=0
    for i in range(ans_len):
        for j in range(26):
            n,seq=memo[temp][j],i+1
            while n<=l:
                n,seq=search(n,seq)
            if seq==ans_len:
                ans+=alpha[j]
                temp=memo[temp][j]
                break
    print(ans)
if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input=sys.stdin.readline
    s=input()
    alpha="abcdefghijklmnopqrstuvwxyz"
    l=len(s)
    alpha2={j:i for i,j in enumerate(alpha)}
    memo=[[0]*26 for _ in range(l,-1,-1)]
    for i in range(26):
        memo[l][i]=l+1
    for x,y in alpha2.items():
        for i in range(l-1,-1,-1):
            if s[i]==x:
                memo[i][y]=i+1
            else:
                memo[i][y]=memo[i+1][y]
    
    search=[1]*(l+2)
    search[l+1]=0
    for i in range(l-1,-1,-1):
        m=max([memo[i][j] for j in range(26)])
        if m!=l+1:
            search[i]=search[m]+1
    
    n,seq=0,0
    ans_len=search[0]
    ans=""
    temp=0
    for i in range(ans_len):
        for j in range(26):
            n=memo[temp][j]
            seq=search[n]+i
            if seq+1==ans_len:
                ans+=alpha[j]
                temp=memo[temp][j]
                break
    print(ans)
if __name__=='__main__':
    main()
### BUGGY CODE ###

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

sorted_x = sorted(X)

l, r = sorted_x[n//2], sorted_x[n//2-1]
for x in X:
    if sorted_x.index(x) < n // 2:
        print(l)
    else:
        print(r)


### FIXED CODE ###

import bisect

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

sorted_x = sorted(X)

l, r = sorted_x[n//2], sorted_x[n//2-1]

for x in X:
    if bisect.bisect_left(sorted_x, x) < n // 2:
        print(l)
    else:
        print(r)
### BUGGY CODE ###

def yakusu(x):
    tmp=int(pow(x, 1/2))+1
    out=set()
    for i in range(1, tmp):
        if x%i==0:
            out.add(i)
            out.add(x//i)
    if pow(x, 1/2)%1==0:
        out.add(pow(x, 1/2))
    out=list(out)
    out.sort()
    return out

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

pairwise=True
X=[1]*(A[-1]+1)  

for a in A:
  tmp=yakusu(a)
  for i in tmp[1:]:
    if X[i]==0:
      pairwise=False
    else:
      for j in range(i, A[-1]+1, i):
        X[i]=0
      
import math
tmp=A[0]+0
for a in A[1:]:
  tmp=math.gcd(tmp, a)
  
if tmp==1:
  setwise=True
else:
  setwise=False
  
if pairwise==True:
  print('pairwise coprime')
elif setwise==True:
  print('setwise coprime')
else:
  print('not coprime')

### FIXED CODE ###

def yakusu(x):
    tmp=int(pow(x, 1/2))+1
    out=set()
    for i in range(1, tmp):
        if x%i==0:
            out.add(i)
            out.add(x//i)
    if pow(x, 1/2)%1==0:
        out.add(pow(x, 1/2))
    out=list(out)
    out.sort()
    return out

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

pairwise=True
X=set()

for a in A:
  tmp=yakusu(a)
  for i in tmp[1:]:
    if i in X:
      pairwise=False
      break
    else:
      X.add(i)
  if pairwise==False:
    break
      
import math
tmp=A[0]+0
for a in A[1:]:
  tmp=math.gcd(tmp, a)
  
if tmp==1:
  setwise=True
else:
  setwise=False
  
if pairwise==True:
  print('pairwise coprime')
elif setwise==True:
  print('setwise coprime')
else:
  print('not coprime')
### BUGGY CODE ###

n = int(input())

p = [int(input()) for _ in range(n)]


# すでに並んでる列
ordered = []
unordered = []

previous = 0
for i in p:
    if previous < i:
        ordered.append(i)
        previous = i
    else:
        unordered.append(i)
        

count = 0

loopc = len(unordered)
for _ in range(loopc):

    center = ordered[len(ordered)//2]

    # センターに近いものを選択
    t = min(unordered, key=(lambda x: abs(x - center)))

    count += 1
    index = 0
    if center > t:
        index = 0
        for i in ordered:
            if i < t:
                count +=1
                index +=1
            else:
                break
    else:
        index = -1
        for i in reversed(ordered):
            if i > t:
                count +=1
                index -=1
            else:
                break


    unordered.remove(t)
    ordered.insert(index, t)

print(count)




### FIXED CODE ###

n = int(input())

p = [int(input()) for _ in range(n)]


# 連続している最大値を求める

lengths = {}
for pn in p:
    if pn in lengths:
        lengths[pn+1] = lengths[pn] + 1
    else:
        lengths[pn+1] = 1
    
max_count = max(lengths.values())
print(n-max_count)
### BUGGY CODE ###

from collections import deque
N=int(input())
A=[int(i) for i in input().split()]
A=[0]+A
for i in range(N):
    A[i+1]+=A[i]
def dou(X):
    n=len(X)
    ma=len(X)-1
    mi=0
    while ma-mi>1:
        mid = (ma + mi)//2
        a=X[n-1]-X[mid]
        b=X[mid-1]-X[0]
        if a>b:
            mi=mid
        else:
            ma=mid
        #print(ma,mi)
    return [X[mi]-X[0],X[n-1]-X[mi]]
num=10**14
K=A[:2]
L=deque(A[2:])
for i in range(2,N-1):
    a=L[0]
    K.append(a)
    #print(K,L)
    ans=[]
    ans=ans+dou(K)+dou(L)
    #print(ans)
    #print(abs(max(ans)-min(ans)))
    num=min(num,abs(max(ans)-min(ans)))
    L.popleft()
print(num)

### FIXED CODE ###

from collections import deque
N=int(input())
A=[int(i) for i in input().split()]
A=[0]+A
for i in range(N):
    A[i+1]+=A[i]
def dou(i,j):
    ma=j
    mi=i
    while ma-mi>1:
        mid = (ma + mi)//2
        a=A[j]-A[mid]
        b=A[mid-1]-A[i]
        if a>b:
            mi=mid
        else:
            ma=mid
        #print(ma,mi)
    return [A[mi]-A[i],A[j]-A[mi]]
num=10**14
for i in range(2,N-1):
    ans=[]
    ans+=dou(0,i)
    ans+=dou(i,N)
    #print(ans)
    t=max(ans)-min(ans)
    num=min(num,t)
print(num)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
ball = []

for i in range(n,0,-1):
    if a[i-1] == 1: 
        ball.append(i)
        for j in range(1,int(i**0.5//1)+1):
            if i%j == 0:
                a[j-1] = 0 if a[j-1] == 1 else 1
                if i/j != j: 
                    a[i//j-1] = 0 if a[i//j-1] == 1 else 1

m = len(ball)
print(m)
if m != 0:
    for b in ball:
        print(b,end=" ")
    else:
        print("")

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
ball = [0]*n
ans = []

for i in range(n,0,-1):
    cnt = 0
    x = i
    while x <= n:
        if ball[x-1] == 1:
            cnt += 1
        x += i
    if cnt%2 != a[i-1]:
        ball[i-1] = 1
        ans.append(i)

m = len(ans)
print(m)
if m != 0:
    for b in ans:
        print(b,end=" ")
    else:
        print("")
### BUGGY CODE ###

H,W = map(int,input().split())
s = [[] for i in range(H)]
for i in range(H): s[i] = list(input())
l = [[0]*W for i in range(H)]
r = [[0]*W for i in range(H)]
d = [[0]*W for i in range(H)]
u = [[0]*W for i in range(H)]

for h in range(H):
    for w in range(W):
        if s[h][w] == ".":
            l[h][w], d[h][w] = 1,1
            if w != 0: l[h][w] = l[h][w-1] + 1
            if h != 0: d[h][w] = d[h-1][w] + 1
    for w in range(W):
        if s[H-1-h][W-1-w] == ".":
            r[H-1-h][W-1-w],u[H-1-h][W-1-w] = 1,1
            if w != 0: r[H-1-h][W-1-w] = r[H-1-h][W-w] + 1
            if h != 0: u[H-1-h][W-1-w] = u[H-h][W-1-w] + 1

ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, l[h][w]+r[h][w]+u[h][w]+d[h][w]-3)

print(ans)
        

### FIXED CODE ###

H,W = map(int,input().split())
s = [[] for i in range(H)]
for i in range(H): s[i] = list(input())
l = [[0]*W for i in range(H)]
r = [[0]*W for i in range(H)]
d = [[0]*W for i in range(H)]
u = [[0]*W for i in range(H)]

for h in range(H):
    if s[h][0] == ".": l[h][0] = 1
    for w in range(1,W):
        if s[h][w] == ".": l[h][w] = l[h][w-1] + 1
    if s[h][W-1] == ".": r[h][W-1] = 1
    for w in range(1,W):
        if s[h][W-1-w] == ".": r[h][W-1-w] = r[h][W-w] + 1

for w in range(W):
    if s[0][w] == ".": d[0][w] = 1
    for h in range(1,H):
        if s[h][w] == ".": d[h][w] = d[h-1][w] + 1
    if s[H-1][w] == ".": u[H-1][w] = 1
    for h in range(1,H):
        if s[H-1-h][w] == ".": u[H-1-h][w] = u[H-h][w] + 1
ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, l[h][w]+r[h][w]+u[h][w]+d[h][w]-3)

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

def judge(n):
    digits = []
    while n != 0:
        r = n % 10
        digits.append(r)
        n = n // 10
    return digits
def main(n):
    sum = 0
    for i in judge(n):
        sum += i
    if sum % 9 == 0:
      print("Yes")
    else:
      print("No")
if __name__=='__main__':
    N = int(input())
    main(N)

### FIXED CODE ###

N = int(input())
if N % 9 == 0:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

import math
a,b,x = map(int, input().split())
def f(a,b,t):
  if t < math.atan(a/b): return a*a*b - a*a*a*math.tan(t)/2
  elif t > math.atan(a/b): return a*b*b*math.tan(math.pi/2-t)/2
  else: return a*a*b/2

eps = 1e-10
err = x-f(a,b,math.atan(a/b))
if abs(err) < eps:
  print(math.degrees(math.atan(a/b)))
else:
  if err > 0:
    ths = [(math.atan(a/b) - 0)*i/3 for i in range(4)]
  else:
    ths = [(math.pi/2-math.atan(a/b))*i/3+math.atan(a/b) for i in range(4)]

  abs_err = [abs(x-f(a,b,th)) for th in ths]
  while min(abs_err) > eps:
    err = [x-f(a,b,th) for th in ths]
    abs_err = list(map(abs,err))
    n_i = err.index(max([e for e in err if e<0]))
    p_i = n_i+1
    ths = [(ths[p_i]-ths[n_i])*i/3+ths[n_i] for i in range(4)]

  print(math.degrees(ths[abs_err.index(min(abs_err))]))

### FIXED CODE ###

from math import tan, pi
a,b,x = map(int, input().split())
eps = 1e-6

def f(a,b,t):
  if pi/2-t<eps: return 0
  if b*tan(pi/2.-t) < a: return b*b*tan(pi/2.-t)/2.*a
  else: return a*a*b - a*a*tan(t)/2.*a
  
th_p, th_n = pi/2, 0.
for i in range(100000):
  th_m = (th_p + th_n)/2.
  err = f(a,b,th_m) - x
  if err**2 < eps**2: break
  elif err < 0: th_p = th_m
  else: th_n = th_m
print(180/pi*th_m)
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

total=0
N=int(input())

for i in range(1,N+1):
    for j in range(1,N+1):
        for k in range(1,N+1):
            total += gcd(i,j,k)
            

print(total)


### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

total=0
N=int(input())

for i in range(1,N+1):
    for j in range(i,N+1):
        if i==j:
            for k in range(j,N+1):
                if j==k:
                    total += gcd(i,j,k)
                else:
                    total += 3*gcd(i,j,k)
        else:
            for k in range(j,N+1):
                if j==k:
                    total += 3*gcd(i,j,k)
                else:
                    total += 6*gcd(i,j,k)
            
print(total)
### BUGGY CODE ###

import math

def move(n):
	twonum = n // 2
	com = 0
	for i in range(twonum + 1):
		up = n - i
		com += math.factorial(up) // (math.factorial(up - i) * math.factorial(i))
	return com

N, M = map(int, input().split())
a = []
a.append(0)
for i in range(M):
	a.append(int(input()))
a.append(N+1)

s = 1
for i in range(M+1):
	step = a[i+1] - a[i] - 1
	m = move(step)
	s = s * m
	a[i+1] += 1

print(s % 1000000007)


### FIXED CODE ###

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

m = []
for i in range(N):
	if i == a[0] - 1:
		del a[0]
		m.append(0)
	elif i == 0:
		m.append(1)
	elif i == 1:
		m.append(m[0]+1)
	else:
		m.append(m[i-1]+m[i-2])

print(m[N-1] % 1000000007)
### BUGGY CODE ###

import sys, heapq, bisect, math, fractions
from collections import deque
from collections import Counter
from collections import OrderedDict

N = int(input())

left = 0
right = N - 1
mid = 0
ll = True
rr = True

for _ in range(20):
    if ll:
        print(left, flush=True)
        l = input()
        if l == "Vacant":
            exit()
        ll = not ll
    if rr:
        print(right, flush=True)
        r = input()
        if r == "Vacant":
            exit()
        rr = not rr

    mid = (r + l) // 2
    print(mid, flush=True)
    m = input()
    if m == "Vacant":
        exit()

    if (mid - left) % 2 == 0 and l != m:
        right = mid
        rr = True
    elif (right - mid) % 2 == 1 and m == r:
        left = mid
        ll = True


### FIXED CODE ###

import sys, heapq, bisect, math, fractions
from collections import deque
from collections import Counter
from collections import OrderedDict

N = int(input())

left = 0
right = N - 1
mid = 0

print(left, flush=True)
l = input()
if l == "Vacant":
    exit()
    
print(right, flush=True)
r = input()
if r == "Vacant":
    exit()

while left + 1 != right:
    mid = (right + left) // 2
    print(mid, flush=True)
    m = input()
    if m == "Vacant":
        exit()
        
    if ((mid - left) % 2 == 0 and l != m) or ((mid - left) % 2 == 1 and l == m):
        right = mid
        r = m
    else:
        left = mid
        l = m
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
A_ = [0] * (N+1)
for a in A:
    A_[a] += 1
A_ = sorted(A_)
c = 0
for i in range(N+1):
    A_[i] = c = A_[i] + c
A_.reverse()

Ans = [float("inf")] * (N+1)
for i in range(N):
    for j, a in enumerate(A_):
        d = a//(i+1)
        #print(d, end=" ")
        Ans[i+j] = min(Ans[i+j], d)
        if d==0:
            break
    #print()
del Ans[-1]
print("\n".join(map(str, Ans)))


### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    C = [0] * (N+1)
    Cnt_A = [0] * (N+1)
    for a in A:
        Cnt_A[a] += 1
        cnt = Cnt_A[a]
        C[cnt] += 1
    cum_C = []
    cu = 0
    for c in C:
        cu += c
        cum_C.append(cu)
    Ans = []
    for k in range(1, N+1):
        # K = k のとき、 n 組以上作れる <=> 使えるカードが nk 枚以上
        # n 組以上作れる <=> 同じカードは n 枚以下
        # 同じカードは n 枚以下で全体として nk 枚以上用意できるか？
        ok, ng = 0, N//k+1
        while ok + 1 < ng:
            n = ok+ng>>1
            if cum_C[n] >= n*k:
                ok = n
            else:
                ng = n
        Ans.append(ok)
    print("\n".join(map(str, Ans)))

main()