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

n,m=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(m)]
from itertools import combinations
#union-find召喚
par=[-1]*n
def find(x):
    if par[x]<0:
        return x
    else:
        par[x]=find(par[x])
        return par[x] #ここ覚えていなかった
def unite(x,y):
    x=find(x)
    y=find(y)
    if x==y:
        False
    else:
        if par[x]>par[y]:#sizeの大きいほうがxにしたい
            x,y=y,x
        par[x]+=par[y]
        par[y]=x
        return True
def same(x,y):
    return find(x)==find(y)
def size(x):
    return -par[find(x)]
comb=list(combinations(range(n),2))
ans=[]

for i in range(m):
    count=0
    num=m-i-1
    unite(AB[num][0]-1,AB[num][1]-1)
    for kumiawase in comb:
        if same(kumiawase[0],kumiawase[1]):
            count+=1
    ans.append(count)
ans=list(reversed(ans))
for i in range(len(ans)-1):
    print(ans[0]-ans[i+1])
print(ans[0])    

### FIXED CODE ###

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

par = [-1] * (n + 1)


def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


def size(x):
    X = find(x)
    return -par[X]


def unite(x, y):
    if find(x) == find(y):
        return False
    X = find(x)
    Y = find(y)
    if size(X) < size(Y):
        x, y = y, x
        X = find(x)
        Y = find(y)
    par[X] += par[Y]
    par[Y] = X
    return True


def is_same(x, y):
    return find(x) == find(y)


def calc(a):
    return a * (a - 1) // 2


goukei = calc(n)
ans = [-1] * (m + 1)
ans[-1] = calc(n)
cnt = 0
AB = [list(map(int, input().split())) for _ in range(m)]
for i in range(m - 1, -1, -1):
    a, b = AB[i]
    if is_same(a, b):
        ans[i] = goukei - cnt
    else:
        A = size(a)
        B = size(b)
        cnt += calc(A + B) - calc(A) - calc(B)
        unite(a, b)
        ans[i] = goukei - cnt
print(*ans[1::], sep="\n")
### BUGGY CODE ###

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


def main():
    from collections import deque

    h, w = map(int, input().split())
    a = [list(input()) for _ in range(h)]
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]
    dist = [[float('inf') for __ in range(w)] for _ in range(h)]
    blacks = deque()

    # See:
    # http://drken1215.hatenablog.com/entry/2019/05/05/223200?_ga=2.177845805.987014750.1556545680-1855989383.1556545680
    # https://blog.kichi2004.jp/2019/05/agc033/
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                dist[i][j] = 0
                blacks.append((i, j))

    while blacks:
        current = blacks.popleft()
        cur_x = current[1]
        cur_y = current[0]

        for i in range(4):
            next_x = cur_x + dx[i]
            next_y = cur_y + dy[i]

            if next_x < 0 or next_x >= w or next_y < 0 or next_y >= h:
                continue

            if dist[next_y][next_x] == float('inf'):
                dist[next_y][next_x] = dist[cur_y][cur_x] + 1
                blacks.append((next_y, next_x))

    ans = 0

    for i in range(h):
        for j in range(w):
            ans = max(ans, dist[i][j])

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

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


def main():
    from collections import deque

    h, w = map(int, input().split())
    a = [list(input()) for _ in range(h)]
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]
    dist = [[-1 for __ in range(w)] for _ in range(h)]
    blacks = deque()

    # See:
    # http://drken1215.hatenablog.com/entry/2019/05/05/223200?_ga=2.177845805.987014750.1556545680-1855989383.1556545680
    # https://blog.kichi2004.jp/2019/05/agc033/
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                dist[i][j] = 0
                blacks.append((i, j))

    while blacks:
        current = blacks.popleft()
        cur_x = current[1]
        cur_y = current[0]

        for i in range(4):
            next_x = cur_x + dx[i]
            next_y = cur_y + dy[i]

            if next_x < 0 or next_x >= w or next_y < 0 or next_y >= h:
                continue

            if dist[next_y][next_x] == -1:
                dist[next_y][next_x] = dist[cur_y][cur_x] + 1
                blacks.append((next_y, next_x))

    ans = 0

    for i in range(h):
        for j in range(w):
            ans = max(ans, dist[i][j])

    print(ans)


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

a=[]
while 1:
    b=input()
    if b[2]=='d':break
    if b[0]=='i':a+=[int(b[7:])]
    else:a.sort();print(a[-1]);a.pop()

### FIXED CODE ###

from heapq import *
a=[]
while 1:
    b=input()
    if b[2]=='d':break
    if b[0]=='i':heappush(a,-int(b[7:]))
    else:print(-heappop(a))
### BUGGY CODE ###

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

sum = 0

for i in range(N):
    for j in range(N - i - 1):
        sum += A[i] * A[N -1 - j]

print(sum % (10**9+7))


### FIXED CODE ###

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

mod = 10 ** 9 + 7
sum = sum(A) **  2

squ = 0
for i in range(N):
    squ +=  A[i] ** 2

answer = int(((sum - squ)  //  2 ) % mod)
print(answer)
### BUGGY CODE ###

N=int(input())
A=[0 for i in range(N)]
for i in range(N):
  A[i]=int(input())
L=A.copy()
L.sort()
max1=L[N-1]
max2=L[N-2]
for i in range(N):
  if i == A.index(max1):
    print(max2)
  else:
    print(max1)

### FIXED CODE ###

N=int(input())
A=[0 for i in range(N)]
for i in range(N):
  A[i]=int(input())
max1=max(A)
numbers_of_max1=0
for i in range(N):
  if A[i]==max1:
    numbers_of_max1+=1
    
if numbers_of_max1>1:
  for i in range(N):
    print(max1)
else:
  L=A.copy()
  L.pop(L.index(max1))
  max2 = max(L)
  for i in range(N):
    if A[i]==max1:
      print(max2)
    else:
      print(max1)
### BUGGY CODE ###

def main():
    N = int(input())
    X = []
    L = []
    for i in range(N):
        x, l = [int(s) for s in input().split()]
        X.append(x)
        L.append(l)

    ranges = []
    for i in range(N):
        ranges.append((X[i] - L[i], X[i] + L[i]))
    ranges.sort(key=lambda x: x[0])

    while True:
        dup = [0 for i in range(len(ranges))]
        for i in range(len(ranges) - 1):
            if ranges[i][1] > ranges[i + 1][0]:
                dup[i] += 1
                dup[i + 1] += 1

        remove_index = [(i, dup[i]) for i in range(len(dup)) if dup[i] > 0]
        if len(remove_index) == 0:
            break
        remove_index.sort(key=lambda x: x[1], reverse=True)
        ranges.pop(remove_index[0][0])
    print(len(ranges))


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N = int(input())
    X = []
    L = []
    for i in range(N):
        x, l = [int(s) for s in input().split()]
        X.append(x)
        L.append(l)

    ranges = []
    for i in range(N):
        ranges.append((X[i] - L[i], X[i] + L[i]))
    ranges.sort(key=lambda x: x[1])

    cnt = len(ranges)
    end = ranges[0][1]
    for i in range(1, len(ranges)):
        if ranges[i][0] < end:
            cnt -= 1
        else:
            end = ranges[i][1]
    print(cnt)


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

x = input().split()  
n,q = int(x[0]), int(x[1])  
a = input() 
l = [] 

for i in range(1,n+1):
  x = a[:i] 
  cnt = x.count('AC') 
  l.append(cnt) 

for i in range(q):
  y = input().split()  
  le,ri = int(y[0]),int(y[1])  
  print(l[ri-1]-l[le-1]) 


### FIXED CODE ###

n,q = map(int, input().split())  
a = input() 
l = [0]*n; 

for i in range(2,n+1):
    x = a[(i-2):i]
    l[i-1] = l[i-2]
    if x=='AC':
        l[i-1] += 1

for i in range(q):
  le,ri = map(int, input().split())  
  print(l[ri-1]-l[le-1])
### BUGGY CODE ###

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

def resolve():
    n=int(input())
    l=list(map(int,input().split()))
    for i in range(1,n):
            print(l[i-1:].count(i))
    print(0)
resolve()

### FIXED CODE ###

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

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

n = int(input())
s = [input() for i in range(n)]
c = 0
 
for i in range(n-1):
  S1 = sorted(s[i])
  for j in range(i+1,n):
    if S1 == sorted(s[j]):
      c += 1
 
print(c)

### FIXED CODE ###

n = int(input())
s = [input() for i in range(n)]
d = {}
c = 0

for i in s:
  tmp = "".join(sorted(i))
  if tmp not in d:
    d[tmp] = 0
  else:
    d[tmp] += 1
  c += d[tmp]
  
print(c)
### BUGGY CODE ###

def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))

    kitai = [0]*1001
    for i in range(1, 1001):
        kitai[i] = (1/2*i*(i+1))/i

    ans = 0
    for i in range(n-k+1):
        wa = 0
        for j in range(k):
            wa += kitai[p[i+j]]
        ans = max(ans, wa)

    print(ans)


main()


### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))

    wa = 0
    for i in range(k):
        wa += p[i]

    m = 0
    a = 0
    for i in range(1, n-k+1):
        wa -= p[i-1]
        wa += p[i+k-1]
        if m < wa:
            a = i
            m = wa

    ans = 0
    for i in range(a, a+k):
        x = p[i]
        ans += (1/2*x*(x+1))/x

    print(ans)


main()
### BUGGY CODE ###

K, S = map(int, input().split())
x,y,z = 0,0,0
ans = 0

for i in range(K+1):
  x = i
  for j in range(S-i+1):
    y = j
    z = S - x - y
    if x + y + z == S and 0 <= x <= K and 0 <= y <= K and 0 <= z <= K:
      ans += 1
print(ans)

### FIXED CODE ###

K, S = map(int,input().split())
ans = 0

for i in range(K+1):
  for j in range(K+1):
    if 0<=S-i-j<=K:
      ans += 1
#    print(i, j, S-i-j, ans)
      

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

M = 10**9 + 7
a = [1] + [0] * 12
p = 1
for c in reversed(input()):
    r = range(10) if c == '?' else (int(c),)
    a = [sum(a[(i - p * j) % 13] for j in r) % M for i in range(13)]
    p = p * 10 % 13
print(a[5])


### FIXED CODE ###

M = 10**9 + 7
a = [1] + [0] * 12
p = 1
for c in reversed(input()):
    r = range(10) if c == '?' else (int(c),)
    a = [sum(a[(i - p * j) % 13] for j in r) % M for i in range(13)]
    p = p * 10 % 13
print(a[5])
### BUGGY CODE ###

K, S = map(int, input().split())

cnt = 0
for x in range(K+1):
  for y in range(K+1):
      if S-(x+y) in range(K+1):
        cnt += 1
print(cnt)

### FIXED CODE ###

K, S = map(int, input().split())

cnt = 0
for x in range(K+1):
  for y in range(K+1):
      if 0 <= S-(x+y) <= K:
        cnt += 1
print(cnt)
### BUGGY CODE ###

import math
X = int(input())
A=[]
B=[]
number = []
flag = 0
for i in range(math.ceil(X/2) * -1, math.ceil(X/2) + 1):
    number.append(i)
    A.append(i ** 5)
    B.append(i ** 5)

for i in range(len(A)):
    for j in range(len(B)):
        if(A[i] - B[j] == X and flag == 0):
            print(number[i],number[j])
            flag += 1

### FIXED CODE ###

X = int(input())
flag = 0
            
#Aの範囲
for i in range(-118, 119):
    for j in range(-119, 118):
        if(i ** 5 - j ** 5 == X and flag == 0):
            print(i, j)
            flag += 1
### BUGGY CODE ###

import re
n,q = map(int,input().split())
s = input()
L = [0]*q
R = [0]*q
for i in range(q):
    L[i],R[i] = map(int,input().split())

dp = [[0]*n for i in range(n)]
for i in range(n):
    for j in range(i+1,n):
        dp[i][j]=len(re.findall(r'AC',s[i:j+1]))

for i in range(q):
    print(dp[L[i]-1][R[i]-1])

### FIXED CODE ###

n,q = map(int,input().split())
s = input()
L = [0]*q
R = [0]*q
for i in range(q):
    L[i],R[i] = map(int,input().split())

dp = [0]*n
for i in range(1,n):
    dp[i]+=dp[i-1]
    if s[i-1:i+1]=='AC':
        dp[i]+=1
for i in range(q):
    print(dp[R[i]-1]-dp[L[i]-1])
### BUGGY CODE ###

N = int(input())
S = input()
total = 0
for i in range(N - 2):
  for j in range(i + 1, N - 1):
    for k in range(j + 1, N):
      if j - i != k - j:
        if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
          total += 1
print(total)

### FIXED CODE ###

N = int(input())
S = input()
r,g,b = 0,0,0
for i in S:
  if i == 'R':
    r += 1
  elif i == 'G':
    g += 1
  else:
    b += 1
minus = 0
for i in range(N - 2):
  for j in range(i + 1, N - 1):
    k = 2 * j - i
    if k >= N:
      continue
    if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
      minus += 1
print(r*g*b - minus)
### BUGGY CODE ###

# coding: utf-8


def solve(*args: str) -> str:
    n, m, k = map(int, args[0].split())
    AB = [tuple(map(int, ab)) for ab in map(str.split, args[1:1+m])]
    CD = [tuple(map(int, cd)) for cd in map(str.split, args[1+m:1+m+k])]

    friends = [set() for _ in range(n+1)]
    blocked = [set() for _ in range(n+1)]

    for a, b in AB:
        friends[a].add(b)
        friends[b].add(a)

    for c, d in CD:
        blocked[c].add(d)
        blocked[d].add(c)

    ret = [0]*(n+1)
    checked = set()
    for a in range(1, n+1):
        if a in checked:
            continue

        chain = set()
        stack = list(friends[a])
        while stack:
            b = stack.pop()
            if b in checked:
                continue

            checked.add(b)
            chain.add(b)
            stack.extend(friends[b]-checked)
        for i in chain:
            ret[i] += len(chain-friends[i]-blocked[i]) - 1

    return ' '.join(map(str, ret[1:]))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


### FIXED CODE ###

# coding: utf-8
from sys import setrecursionlimit


def dfs(node: int):
    if checked[node]:
        return

    checked[node] = True
    chain.add(node)
    for n in friends[node]:
        dfs(n)


def solve(*args: str) -> str:
    setrecursionlimit(2 * 10 ** 9)
    n, m, k = map(int, args[0].split())

    global friends
    friends = {i: set() for i in range(n+1)}
    blocked = {i: set() for i in range(n+1)}

    for a, b in map(str.split, args[1:1+m]):
        friends[int(a)].add(int(b))
        friends[int(b)].add(int(a))

    for c, d in map(str.split, args[1+m:1+m+k]):
        blocked[int(c)].add(int(d))
        blocked[int(d)].add(int(c))

    global checked
    checked = [False]*(n+1)

    ret = [0]*(n+1)
    for a in range(1, n+1):
        if checked[a]:
            continue

        global chain
        chain = set()
        dfs(a)
        count = len(chain) - 1
        for i in chain:
            ret[i] += count - len(chain & (friends[i] | blocked[i]))

    return ' '.join(map(str, ret[1:]))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
### BUGGY CODE ###

S=str(input())
k=len(S)
count=0
for i in range(k-4):
    for j in range(k-4):
        if i+j+4>k:
            continue
        n=int(S[j:i+j+4])
        if n%2019==0:
            count+=1
print(count)


### FIXED CODE ###

S=str(input())
n=len(S)
mod=2019
ans=0
mod_set=[0]*mod
mod_set[0]+=1
ten=1
k=0
for i in range(n-1,-1,-1):
    k=(k+ten*int(S[i]))%mod
    mod_set[k]+=1
    ten=(ten*10)%mod

for i in mod_set:
    ans+=i*(i-1)//2
print(ans)
### BUGGY CODE ###

n = int(input())
A = [int(input()) for _ in range(n)]
B = []
cnt = 0
i = 0
while i != 1:
    i = A[i]-1
    B.append(i)
    cnt += 1
    if len(B) != len(set(B)):
        print(-1)
        exit()
print(cnt)


### FIXED CODE ###

n = int(input())
A = [int(input()) for _ in range(n)]
B = []
cnt = 0
i = 0
while i != 1:
    i = A[i]-1
    B.append(i)
    cnt += 1
    if cnt > 10**5 + 1:
        print(-1)
        exit()
print(cnt)
### BUGGY CODE ###

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

N = int(input())
S = list(input())
ans = [""] * N

for i in range(N):
    ans[i] = S[:i].count('W') + S[(i+1):].count('E')

print(min(ans))

### FIXED CODE ###

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

N = int(input())
S = input()
cnt = [0] * (N+1)
cnt[0] = 0
ans = N

for i in range(N):
    cnt[i+1] = cnt[i]
    if S[i] == 'W':
        cnt[i+1] += 1

for j in range(1, N+1):
    ans = min(ans, cnt[j-1] + (N - j) - (cnt[N]-cnt[j]))

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

n = int(input())
As = [list(map(int, input().split())) for _ in range(n)]

import copy
d = copy.deepcopy(As)
for i in range(n):
    for k in range(n):
        for j in range(n):
            d[i][j] = min(d[i][j], d[i][k]+d[k][j])
cnt = 0
routes = set()
for i in range(n):
    for j in range(i+1,n):
        routes.add(i*n+j)


for i in range(n):
    for k in range(n):
        for j in range(n):
            x = (i-j)*(j-k)*(k-i)
            # かぶりを消す
            if d[i][j] == d[i][k]+d[k][j] and x != 0:
                try:
                    routes.remove(i*n+j)
                except:
                    pass
cnt = 0
for r in routes:
    i,j = divmod(r,n)
    cnt += d[i][j]

if As != d:
    print(-1)
else:
    print(cnt)

### FIXED CODE ###

n = int(input())
As = [list(map(int, input().split())) for _ in range(n)]

import copy
d = copy.deepcopy(As)
for i in range(n):
    for k in range(n):
        for j in range(n):
            d[i][j] = min(d[i][j], d[i][k]+d[k][j])
cnt = 0
routes = set()
for i in range(n):
    for j in range(i+1,n):
        routes.add(i*n+j)


for i in range(n):
    for k in range(n):
        for j in range(n):
            x = (i-j)*(j-k)*(k-i)
            # かぶりを消す
            if d[i][j] == d[i][k]+d[k][j] and x != 0:
                try:
                    routes.remove(i*n+j)
                except:
                    pass
cnt = 0
for r in routes:
    i,j = divmod(r,n)
    cnt += d[i][j]

if As != d:
    print(-1)
else:
    print(cnt)
### BUGGY CODE ###

S = list(input())[::-1]
L = len(S)
from collections import defaultdict

mod = 2019
t = 0
dic = defaultdict(int)
ans = 0
for l in range(L):
    t += pow(10, l)*int(S[l])
    i = t%mod
    ans += dic[i]
    dic[i] += 1
    if i==0:
        ans += 1

print(ans)

### FIXED CODE ###

S = list(input())[::-1]
L = len(S)
from collections import defaultdict

mod = 2019
t = 0
dic = defaultdict(int)
ans = 0
for l in range(L):
    t += pow(10, l, mod)*int(S[l])%mod
    t %= mod
    ans += dic[t]
    dic[t] += 1
    if t==0:
        ans += 1

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

n, q = map(int, input().split())
S = input() + 'X'
T = [0]*n
for i in range(n):
    s = S[i:i+2]
    if s == 'AC':
        T[i] = 1
for _ in range(q):
    l,r = map(int, input().split())
    print(sum(T[l-1:r-1]))

### FIXED CODE ###

n, q = map(int, input().split())
S = 'X' + input()
T = [0]*(n+1)
for i in range(n):
    s = S[i:i+2]
    if s == 'AC':
        T[i+1] = T[i] + 1
    else:
        T[i+1] = T[i]
for _ in range(q):
    l,r = map(int, input().split())
    print(T[r]-T[l])
### BUGGY CODE ###

import math
n=int(input())
lim=math.ceil(math.sqrt(n))

for i in range(lim, n+1):
  if n%i==0:
    print(len(str(i)))
    exit()
  elif (n+1)/2<i:
    print(len(str(n)))
    exit()
    


### FIXED CODE ###

n=int(input())
l=int((n**0.5))+1
ans=n
for i in range(1, l+1):
  if n%i==0:
    ans=min(ans, len(str(n//i)))
print(ans)
### BUGGY CODE ###

length = 2010

n = int(input())
L = list(map(int, input().split()))
ans = 0
L.sort()
sum_1 = [ 0 for _ in range(length)]
for i in range(n):
    sum_1[L[i]]+=1
#棒の長さで累積和
for i in range(length-1):
    sum_1[i+1] +=sum_1[i]
for i in range(n-1):
    for j in range(i+1, n):
        a = abs(L[i]-L[j])
        b = L[i]+L[j]
        ans = ans + sum_1[b-1] - sum_1[a]

        if a<L[i] and L[i]<b:
            ans -=1
        
        if a<L[j] and L[j]<b:
            ans -=1
print(ans//3)

### FIXED CODE ###

import bisect

n = int(input())
l = list(map(int, input().split()))
ans = 0
l.sort()
for i in range(n-1, -1, -1):
    a = l[i]
    for j in range(i-1, -1, -1):
        b = l[j]
        c = bisect.bisect_right(l, a-b, lo=0, hi=j)
        ans = ans + j-c
print(ans)
### BUGGY CODE ###

N = int(input())
cap = [int(input()) for i in range(5)]
state = [N, 0, 0, 0, 0, 0]
time = 0
while state[-1] != N:
    for i in range(4,-1,-1):
        if state[i]==0:
            continue
        move = cap[i] if state[i]>=cap[i] else state[i]
        state[i] -= move
        state[i+1] += move
    time += 1
print(time)

### FIXED CODE ###

import math
N = int(input())
cap = [int(input()) for i in range(5)]
print( math.ceil(N/min(cap))+4)
### BUGGY CODE ###

mod = 10**9 + 7
n = int(input())
lx = list(map(int, input().split()))

from math import factorial as kj

d = 0
ans = 0

for i in range(1, n):
  d += kj(n-1) // i % mod
  ans = (ans + (lx[i] - lx[i-1]) * d) % mod

print(ans)

### FIXED CODE ###

mod = 10**9 + 7
n = int(input())
lx = list(map(int, input().split()))

d = 0
ans = 0

for i in range(1, n):
  f = 1 if i == 1 else f * (i-1) % mod
  d = (d * i + f) % mod
  ans = (ans * i + (lx[i] - lx[i-1]) * d) % mod

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

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

### FIXED CODE ###

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

N=int(input())
alist=list(map(int, input().split()))
alist.sort()
for i in range(1,N+1):
    if i in alist:
        ans=alist.count(i)
        print(ans)
        alist=alist[ans:]
    else:
        print(0)


### FIXED CODE ###

N=int(input())
alist=list(map(int, input().split()))
anslist=[0]*N
for a in alist:
    anslist[a-1]+=1
for ans in anslist:
    print(ans)
### BUGGY CODE ###

n = int(input())
nums = list(map(int,input().split()))
nums.sort()
ans = 0
cnt = {}
div = []
for i in nums:
  cnt[i] = cnt.get(i,0) + 1
  flag = 0
  for j in div:
    if i%j == 0:
      flag = 1
      break
  if flag == 0: 
    div.append(i)
    
for i in div:
  if cnt[i] == 1:
    ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
nums = list(map(int,input().split()))
nums.sort()
ans = 0
cnt = {}
flag = [0]*1000005
for i in nums:
  cnt[i] = cnt.get(i,0) + 1

for i in nums:
  if flag[i] == 0 and cnt[i] == 1:
    ans += 1
  if flag[i] == 1:
    continue
  for j in range(i,1000001,i):
    flag[j] = 1

print(ans)