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

import sys
from collections import Counter

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def main():
    s = input()
    N = len(s)
    K = ii()

    A = set()

    for i in range(N):
        for j in range(i, N):
            A.add(s[i:j+1])

    A = list(A)
    A.sort()

    print(A[K-1])



if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import Counter

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def main():
    s = input()
    N = len(s)
    K = ii()

    A = set()
    for i in range(N):
        for j in range(K):
            A.add(s[i:i+j+1])
    A = list(A)
    A.sort()
    print(A[K-1])


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

N, Q = map(int, input().split())
l=[None]*N
l[0]=[1,1,0]
for i in range(1,N):
    a,b=map(int,input().split())
    l[i]=[b,a,0]
l.sort()
for i in range(Q):
    p,x=map(int,input().split())
    l[p-1][2]+=x
for i in range(N):
    s=i+1
    t=l[0][2]
    while s!=1:
        t+=l[s-1][2]
        s=l[s-1][1]
    print(t,end=" ")

### FIXED CODE ###

N,Q=map(int,input().split())
l=[[1,0,0]]
for i in range(1,N):
    a,b=map(int,input().split())
    l.append([b,a,0])
l.sort()
for i in range(Q):
    p,x=map(int,input().split())
    l[p-1][2]+=x
t=[l[0][2]]
for i in range(1,N):
    t.append(t[l[i][1]-1]+l[i][2])
print(*t)
### BUGGY CODE ###

import itertools

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

for k in range(N):
    l = sorted([A[i] for i in range(N) if i!=k])
    counter = 0
    result = 0
    for i in range(len(l)):
        counter += 1
        if i!=len(l)-1:
            if l[i] != l[i+1]:
                #print(l[i],counter)
                result += len(list(itertools.combinations(range(counter),2)))
                counter = 0
        else:
            #print(l[i],counter)
            result += len(list(itertools.combinations(range(counter),2)))
    print(result)

### FIXED CODE ###

from collections import Counter

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

l = Counter(A)
ans = sum([v*(v-1)//2 for v in l.values()])

for a in A:
    print(ans - l[a]*(l[a]-1)//2 + (l[a]-1)*(l[a]-2)//2)
### BUGGY CODE ###

import numpy as np

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

tmp = [[0 for i in range(N)] for i in range(N)]
for i in range(N):
    tmp[i][i] = 1
    tmp[i][(i+1)%N] = 1

A = np.matrix(tmp)
Y = np.matrix(W).T

ans = np.linalg.solve(A, Y)*2

tmp = []
for a in ans:
    tmp.append(str(int(a)))

print(" ".join(tmp))

### FIXED CODE ###

import numpy as np

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

ans = []

ans.append(str(sum(W) - 2 * sum([W[i] for i in range(N) if i % 2 == 1])))

for i in range(1, N):
    ans.append(str( 2*W[i-1] - int(ans[i-1])))

print(" ".join(ans))
### BUGGY CODE ###

x,k,d=map(int,input().split())
x=abs(x)

if x-k*d>=0:
    print(x-k*d)
else:
    a=x
    while a>d:
        a-=d
        k-=1
    if k%2==0:
        print(min(a,2*d-a))
    else:
        print(min(d-a,a+d))

### FIXED CODE ###

x,k,d=map(int,input().split())
x=abs(x)

if x-k*d>=0:
    print(x-k*d)
else:
    n=x//d
    k-=n
    a=x-n*d
    if k%2==0:
        print(min(a,2*d-a))
    else:
        print(min(d-a,a+d))
### BUGGY CODE ###

a, b = map(int, input().split())
def kansu_return_flag(a,b):
    ans = 0
    flag = 0
    if a>b:
        big = a
        small = b
    else:
        big = b
        small = a
        
    for i in range(small,big):
        a_ans = abs(big-i)
        b_ans = abs(small-i)
        if a_ans == b_ans:
            ans = i
            flag = 1
            break
    return flag,ans

flag,ans = kansu_return_flag(a,b)

if flag == 1:
    print(ans)
else:
    print('IMPOSSIBLE')

### FIXED CODE ###

a, b = map(int, input().split())
def kansu_return_flag(a,b):
    ans = 0
    flag = 0

    if abs(a-b)%2 != 0:
        flag = 0
    else:
        ans = (a+b)/2
        flag = 1
    return flag,ans

flag,ans = kansu_return_flag(a,b)

if flag == 1:
    print(int(ans))
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

n,m=map(int,input().split())
ac=[]
wa=[0]*n
a=0
w=0
for i in range(m):
    l=input().split()
    if ac.count(l[0])==0:
        if l[1]=='AC':
            ac.append(l[0])
            a+=1
            w+=wa[int(l[0])-1]
        else:
            wa[int(l[0])-1]+=1
    if a==n:
        break
print(a,w)


### FIXED CODE ###

n,m=map(int,input().split())
ac={}
wa=[0]*n
a=0
w=0
for i in range(n):
    ac[i+1]=0
    
for i in range(m):
    l=input().split()
    if ac[int(l[0])]!='AC':
        if l[1]=='AC':
            ac[int(l[0])]='AC'
            a+=1
            w+=wa[int(l[0])-1]
        else:
            wa[int(l[0])-1]+=1
    if a==n:
        break
print(a,w)
### BUGGY CODE ###

def main():
    MOD = 998244353

    N, S = map(int, input().split())
    A = tuple(map(int, input().split()))

    DP = [[[0] * 3 for _ in range(S + 1)] for _ in range(N + 1)]
    DP[0][0][0] = 1

    for i in range(N):
        DP[i + 1][0][0] = DP[i][0][0] 
        DP[i + 1][0][1] = DP[i][0][0] + DP[i][0][1]
        a = A[i]
        if a > S:
            for j in range(1, S + 1):
                DP[i + 1][j][1] = (DP[i][j][0] + DP[i][j][1]) % MOD #以前から合計jになっている場合のみOK
        else:
            for j in range(1, a):
                DP[i + 1][j][1] = (DP[i][j][0] + DP[i][j][1]) % MOD #以前から合計jになっている場合のみOK
            for j in range(a, S + 1):
                DP[i + 1][j][1] = (DP[i][j][0] + DP[i][j][1] + DP[i][j - a][0] + DP[i][j - a][1]) % MOD

        DP[i + 1][S][2] = (DP[i][S][1] + DP[i][S][2]) % MOD
        if a <= S:
            DP[i + 1][S][2] += DP[i][S - a][0] + DP[i][S - a][1]
        DP[i + 1][S][2] %= MOD

    print (DP[N][S][2])

    # for i in range(N + 1):
    #     print (DP[i])

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    MOD = 998244353

    N, S = map(int, input().split())
    A = tuple(map(int, input().split()))

    DP0 = [[0] * (S + 1) for _ in range(N + 1)]
    DP1 = [[0] * (S + 1) for _ in range(N + 1)]
    DP2 = [[0] * (S + 1) for _ in range(N + 1)]

    DP0[0][0] = 1

    for i in range(N):
        DP0[i + 1][0] = DP0[i][0] 
        DP1[i + 1][0] = DP0[i][0] + DP1[i][0]
        a = A[i]
        if a > S:
            for j in range(1, S + 1):
                DP1[i + 1][j] = DP1[i][j] #以前から合計jになっている場合のみOK
        else:
            for j in range(1, a):
                DP1[i + 1][j] = DP1[i][j] #以前から合計jになっている場合のみOK
            for j in range(a, S + 1):
                DP1[i + 1][j] = (DP1[i][j] + DP0[i][j - a] + DP1[i][j - a]) % MOD
                # DP[i + 1][j][1] = (DP[i][j][0] + DP[i][j][1] + DP[i + 1][j - a][1]) % MOD

        DP2[i + 1][S] = (DP1[i][S] + DP2[i][S])
        if a <= S:
            DP2[i + 1][S] += DP0[i][S - a] + DP1[i][S - a]
        DP2[i + 1][S] %= MOD

    print (DP2[N][S])

    # for i in range(N + 1):
    #     print (DP[i])

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

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(n**(1/2)) + 1):
        if n % k == 0:
            return False

    return True

Q = int(input())

ans = []
for i in range(Q):
    l, r = map(int, input().split())

    cnt = 0
    for j in range(l, r+1):
        if is_prime(j) and is_prime((j+1)//2):
            cnt += 1
    ans.append(cnt)

for a in ans:
    print(a)


### FIXED CODE ###

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return is_prime

is_prime = primes(10**5)
like = [False] * 10**5
for i in range(3, 10**5, 2):
    if is_prime[i] and is_prime[(i+1)//2]:
        like[i] = True

cusum = [0] * 10**5
for i in range(3, 10**5, 2):
    cusum[i] = cusum[i-2] + like[i]

Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())

    if l == 1:
        print(cusum[r])
    else:
        print(cusum[r] - cusum[l-2])
### BUGGY CODE ###

n=int(raw_input())
a=[]
for i in range(n):
    a.append(int(raw_input()))

for i in range(n):
    m=0
    for j in range(n):
        if i == j:
            continue
        m=max(m,a[j])
    print m



### FIXED CODE ###

n=int(raw_input())
a=[]
for i in range(n):
    a.append(int(raw_input()))

m=max(a)
c=a.count(m)

if c > 1:
    for i in range(n):
        print m
else:
    s=sorted(a)[-2]
    for i in range(n):
        if a[i] != m:
            print m
        else:
            print s
### BUGGY CODE ###

import sys
H, W = map(int, input().split())
S = [line.strip("\n") for line in sys.stdin]
transposeS = ["" for _ in range(W)]

rowRunLength = [[0] * W for _ in range(H)]
columnRunLength = [[0] * H for _ in range(W)]


for rowNum, elem in enumerate(S):
    previousObstacleIndex = -1
    lightCount = 0
    for colNum, char in enumerate(elem):
        if char == "#":
            rowRunLength[rowNum][colNum] = 0
            for i in range(previousObstacleIndex + 1, colNum):
                rowRunLength[rowNum][i] = lightCount
            previousObstacleIndex = colNum
            lightCount = 0
        else:
            lightCount += 1
    else:
        for i in range(previousObstacleIndex + 1, W):
            rowRunLength[rowNum][i] = lightCount

for i in range(W):
    for j in range(H):
        transposeS[i] += S[j][i]

for rowNum, elem in enumerate(transposeS):
    previousObstacleIndex = -1
    lightCount = 0
    for colNum, char in enumerate(elem):
        if char == "#":
            columnRunLength[rowNum][colNum] = 0
            for i in range(previousObstacleIndex + 1, colNum):
                columnRunLength[rowNum][i] = lightCount
            previousObstacleIndex = colNum
            lightCount = 0
        else:
            lightCount += 1
    else:
        for i in range(previousObstacleIndex + 1, H):
            columnRunLength[rowNum][i] = lightCount

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            ans = max(ans, rowRunLength[i][j] + columnRunLength[j][i] - 1)

print(ans)


### FIXED CODE ###

# can't AC without numpy, Python array handling with for is SLOW
import numpy as np
H, W = map(int, input().split())
S = []
for _ in range(H):
    S.append(list(input()))
S = (np.array(S) == ".") * 1

# i行j列に置いたとき上下左右の方向それぞれに光の軌跡が何マス伸びるか(自マスを含む)
trailLeft = np.zeros((H, W), dtype=int)
trailRight = np.zeros((H, W), dtype=int)
trailUp = np.zeros((H, W), dtype=int)
trailDown = np.zeros((H, W), dtype=int)

for i in range(H):
    if i == 0:
        trailUp[i] = S[i]
        trailDown[H - i - 1] = S[H - i - 1] * 1
    else:
        trailUp[i] = (trailUp[i - 1] + 1) * S[i]
        trailDown[H - i - 1] = (trailDown[H - i] + 1) * S[H - i - 1]

for j in range(W):
    if j == 0:
        trailLeft[:, j] = S[:, j]
        trailRight[:, W - j - 1] = S[:, W - j - 1] * 1
    else:
        trailLeft[:, j] = (trailLeft[:, j - 1] + 1) * S[:, j]
        trailRight[:, W - j - 1] = (trailRight[:, W - j] + 1) * S[:, W - j - 1]

print(np.max(trailLeft + trailRight + trailUp + trailDown - 3))
### BUGGY CODE ###

import math

N = int(input())
A = [int(i) for i in input().split()]

A_ = [A[i] - i for i in range(N)]

A_max = max(A_) + 1
A_min = min(A_) - 1

A_b = [sum([abs(a - i) for a in A_]) for i in range(A_min, A_max+1)]

print(min(A_b))


### FIXED CODE ###

import math

def median(l):
    n = len(l)
    ls = sorted(l)
    if n%2 == 0:
        m1 = ls[int(n/2)-1]
        m2 = ls[int(n/2)]
        return (m1+m2)/2
    
    return ls[int(n/2)]

N = int(input())
A = [int(i) for i in input().split()]

A_ = [A[i] - i - 1 for i in range(N)]

A_m = median(A_)
A_m1 = math.floor(A_m)
A_m2 = math.ceil(A_m)

A_b = [sum([abs(a - i) for a in A_]) for i in (A_m1, A_m2)]

print(min(A_b))
### BUGGY CODE ###


def sign(x):
    return (x > 0) - (x < 0)


def main():
    _ = int(input())
    a = map(int, input().split())
    ans = []
    arr = []
    for an in a:
        if len(arr) < 2:
            arr.append(an)
        else:
            state = sum([el - arr[i] for i, el in enumerate(arr[1:])])
            if state == 0:
                arr.append(an)
            else:
                current = an - arr[-1]
                if current == 0 or sign(state) == sign(current):
                    arr.append(an)
                else:
                    ans.append(arr)
                    arr = [an]
    ans.append(arr)

    print(len(ans))


if __name__ == '__main__':
    main()


### FIXED CODE ###


def sign(x):
    return (x > 0) - (x < 0)


def main():
    _ = int(input())
    a = map(int, input().split())
    ans = []
    arr = []
    state = 0
    for an in a:
        if len(arr) < 2:
            arr.append(an)
        else:
            state += (arr[-1] - arr[-2])
            if state == 0:
                arr.append(an)
            else:
                current = an - arr[-1]
                if current == 0 or sign(state) == sign(current):
                    arr.append(an)
                else:
                    ans.append(arr)
                    arr = [an]
                    state = 0
    ans.append(arr)

    print(len(ans))


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

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7


R, G, B, N = MAP()
count = 0
for i in range(N+1):
	for j in range(int((N-i*R)//G)+1):
		r = i
		g = j
		b = int(max(0, (N - r*R - g*G))/B)
		# print(r, g, b)
		if R*r + G*g + B*b == N:
			count += 1
print(count)


### FIXED CODE ###

import sys, re

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7


R, G, B, N = MAP()
count = 0
for i in range(N+1):
	for j in range(int((N-i*R)//G)+1):
		# print(r, g, b)
		# if R*i + G*j + B*int(max(0, (N - i*R - j*G))/B) == N:
		# 	count += 1
		if (N - i*R - j*G) % B == 0:
			count += 1
print(count)
### BUGGY CODE ###

N = input()
A = [int(i) for i in input().split()]

for i in range(len(A)):
    B = A[:i] + A[i+1:]
    B.append(0)
    B = [0] + B
    ans = 0
    for x, y in zip(B[:-1], B[1:]):
        ans += abs(x-y)
    print(ans)



### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]

B = [0] + A + [0]
ans = 0
for x, y in zip(B[:-1], B[1:]):
    ans += abs(x-y)
for i in range(N):
    print(ans - abs(B[i+1]-B[i]) - abs(B[i+2]-B[i+1]) + abs(B[i+2]-B[i]))
### BUGGY CODE ###

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

N = int(input())
s = input()
Q = int(input())


def convert(s: str, q1: int, q2: str):
    return s[:q1] + q2 + s[q1+1:]


def calc(s: str, q1: int, q2: int):
    res = list(set(s[q1:q2+1]))
    # checks = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n','o', 'p', 'q',
    #           'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
    # res = np.array([check(set_s, l) for l in checks])

    # print(res)
    return len(res)


def check(s, check_str: str):
    if s in check_str:
        return 1
    return 0


for _ in range(Q):
    q, q1, q2 = input().split()
    q = int(q)
    if q == 1:
        s = convert(s, int(q1) - 1, q2)
    if q == 2:
        print(calc(s, int(q1) - 1, int(q2) - 1))


### FIXED CODE ###

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

'''
7
abcdbbd
6
2 3 6
1 5 z
2 1 1
1 4 a
1 7 d
2 1 7
'''

# from helper import elapsed_time
from bisect import bisect_left, insort_left


N = int(input())
s = list(input())
Q = int(input())

# a-zまでの26文字に対して、s文字列の各文字に該当するindexを格納しておく
d = {i: [] for i in range(26)}
for i, c in enumerate(s):
    d[ord(c) - ord("a")].append(i)


# @elapsed_time
def convert(d: dict, s: list, q1: int, q2: str):
    if s[q1] == q2:
        return d, s

    didx_before = ord(s[q1]) - ord("a")
    didx_after = ord(q2) - ord("a")

    idx = bisect_left(d[didx_before], q1)
    d[didx_before].pop(idx)
    s[q1] = q2
    insort_left(d[didx_after], q1)

    return d, s


# @elapsed_time
def calc(d: dict, q1: int, q2: int):
    ans = 0
    for i in range(26):
        idx = bisect_left(d[i], q1)
        if d[i] and q1 <= d[i][-1] and d[i][idx] < q2 + 1:
            ans += 1

    return ans


for _ in range(Q):
    q, q1, q2 = input().split()
    q = int(q)
    if q == 1:
        d, s = convert(d, s, int(q1) - 1, q2)
    if q == 2:
        print(calc(d, int(q1) - 1, int(q2) - 1))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())
s = input().rstrip()

strings = [[] for _ in range(n // 2 + 1)]

for i in range(n):
    string = [s[i]]
    strings[1].append(s[i])
    for j in range(i + 1, n):
        string.append(s[j])
        if j - i + 1 < 1 + n // 2:
            strings[j - i + 1].append("".join(string))

ans = 0

for i in range(n // 2, 0, -1):
    check = strings[i]
    for j in range(len(check)):
        if check[j] in check[j + i:]:
            print(i)
            sys.exit()

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
s = input().rstrip()

def z_algo(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A

ans = 0

for i in range(n):
    s_ = s[i:]
    z_s = z_algo(s_)
    for j in range(len(z_s)):
        ans = max(ans, min(j, z_s[j]))

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

import numpy as np

N = int(input())
p = [0] + list(input().split())

for i in range(1, N+1):
    item = p[i].replace('0.', '')
    p[i] = int(item)

#print(p)

dp = np.zeros((3100, 3100))
#dp[i, j] = i枚目までのコインを投げて，表の個数がj枚である確率 * (10**(2*i))
#pythonのlistだと遅いので，numpyにおけるベクトル漸化式としてdpを埋めていく

dp[1, 0] = 100-p[1]
dp[1, 1] = p[1]

for i in range(2, N + 1):
    for j in range(i+1):
        dp[i] = (np.roll(dp[i-1], 1) * p[i] + dp[i-1] * (100-p[i]))
        #dp[i][j] = i-1枚目までで表がj-1かつi回目で表　＋　i-1回目までで表がj枚かつi回目で裏（MECE）
        #print(i, j, dp[i][j])
        #プログラムの仕組み上，iが一つ進むと，100 * 100 = 10**4　ずつスケールが大きくなっていく。10**20で打ち切る。


ans = 0

for k in range(-(-N//2), N+1):
    ans += dp[N, k]

print(ans/10**(2*N))

### FIXED CODE ###

import numpy as np

N = int(input())
p = [0] + list(map(float, input().split()))

dp = np.zeros((3100, 3100))
#dp[i, j] = i枚目までのコインを投げて，表の個数がj枚である確率
#pythonのlistだと遅いので，numpyにおけるベクトル漸化式としてdpを埋めていく

dp[1, 0] = 1-p[1]
dp[1, 1] = p[1]

for i in range(2, N + 1):
    dp[i] = np.roll(dp[i-1], 1) * p[i] + dp[i-1] * (1-p[i])
    #dp[i][j] = i-1枚目までで表がj-1かつi回目で表　＋　i-1回目までで表がj枚かつi回目で裏（MECE）
    #つまり，dp[i][j] = dp[i-1][j-1] * p[i] + dp[i-1][j] * (1 - p[i])
    #numpyを使ってベクトル漸化式と見ることで，for_loopを一層分解消。
    #print(i, j, dp[i][j])

ans = 0

for k in range(-(-N//2), N+1):
    ans += dp[N, k]

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

import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)
s=input()
t=input()
@lru_cache(None)
def dp(i,j):
  if i==0 or j==0:
    return ""
  if s[i-1]==t[j-1]:
    return ''.join([dp(i-1,j-1)+s[i-1]])
  else:
    return dp(i,j-1) if len(dp(i,j-1))>=len(dp(i-1,j)) else dp(i-1,j)
print(dp(len(s),len(t)))
    

### FIXED CODE ###

import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)
s=input()
t=input()
dp=[[0 for i in range(len(t)+1)] for j in range(len(s)+1)]
for i,sele in enumerate(s):
  for j ,tele in enumerate(t):
    if sele==tele:
      dp[i+1][j+1]=dp[i][j] +1
    else :
      dp[i+1][j+1]=dp[i+1][j] if dp[i+1][j]>=dp[i][j+1] else dp[i][j+1]     
res=""
i=len(s)
j=len(t)
#print(dp)
while True:
#for k in range(9):
  #rint(i,j,dp[i][j])
  if i-1>=0:
    if dp[i-1][j]==dp[i][j]:
      i=i-1
      continue
  if j-1>=0:
    if dp[i][j-1]==dp[i][j]:
      j=j-1
      continue
  if i-1>=0 and j-1>=0:
    if dp[i-1][j-1]==dp[i][j]-1:
      j=j-1
      i=i-1
      res=s[i]+res
      #print(i,res)
      if dp[i][j]==0:
        break
      continue
  break
print(res)
### BUGGY CODE ###

N = int(input())
Mgr = [int(num) for num in input().split()]

for i in range(1, N+1):
        ans = Mgr.count(i)
        print(ans)


### FIXED CODE ###

N = int(input())
Mgr = [int(num) for num in input().split()]
sub = [0]*N

for i in range(len(Mgr)):
    sub[Mgr[i]-1] += 1

for i in range(N):
    print(sub[i])
### BUGGY CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()

    y = [0] * (10**6 + 1)
    A = []
    for x in sys.stdin.readline().split():
        x = int(x)
        A.append(x)
        y[x] += 1

    ans = 0
    for i in range(N):
        x = A[i]
        if x > 1:
            if y[1] : continue
        if y[x] > 1: continue

        f = 1
        for j in range(2,int(math.sqrt(x))+1):
            if x % j == 0 and (y[j] or y[x//j]):
                f = 0
                break
        ans += f

    print(ans)
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()

    y = [0] * (10**6 + 1)
    z = [0] * (10**6 + 1)
    A = []
    for x in sys.stdin.readline().split():
        x = int(x)
        A.append(x)
        y[x] += 1
        if y[x] == 1:
            c = x * 2
            while c <= 10**6:
                z[c] = 1
                c += x

    ans = 0
    for i in range(N):
        x = A[i]
        if y[x] > 1: continue

        if z[x] == 0:
            ans += 1

    print(ans)
if __name__ == '__main__':
    main()