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

import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))


def solve():
    n, k = nm()
    a = nl()
    a.sort()

    lef = [1]*n
    rig = [1]*n
    mask = (1 << (k+1)) - 1
    for i in range(n-1):
      lef[i+1] = lef[i] | (lef[i] << a[i]) & mask
      rig[-i-2] = rig[-i-1] | (rig[-i-1] << a[-i-1]) & mask

    ok = -1
    ng = n
    while ng - ok > 1:
      mid = (ng + ok) // 2
      lc = lef[mid]
      rc = rig[mid]
      cov = ((1 << k) - 1) ^ ((1 << max(k - a[mid], 0)) - 1)
      for i in range(k):
        if lc & 1 and rc & cov:
          ng = mid
          break
        lc >>= 1
        cov >>= 1
      else:
        ok = mid
    print(ok + 1)
    return

solve()


### FIXED CODE ###

n, k = map(int,input().split())
a = [k+1 if x > k else x for x in map(int,input().split())]
a.sort()
lef = [1]*n
rig = [1]*n
mask = (1 << (k+1)) - 1
for i in range(n-1):
  lef[i+1] = lef[i] | (lef[i] << a[i]) & mask
  rig[-i-2] = rig[-i-1] | (rig[-i-1] << a[-i-1]) & mask
ok = -1
ng = n
while ng - ok > 1:
  mid = (ng + ok) // 2
  if a[mid] >= k:
      ng = mid
      continue
  lc = lef[mid]
  rc = rig[mid]
  cov = ((1 << k) - 1) ^ ((1 << (k - a[mid])) - 1)
  for i in range(k):
    if lc & 1 and rc & cov:
      ng = mid
      break
    lc >>= 1
    cov >>= 1
  else:
    ok = mid
print(ok + 1)
### BUGGY CODE ###

N, M = map(int, input().split())

id_list = []
for i in range(1, N + 1):
    id_list.append(i)

for _ in range(M):
    L, R = map(int, input().split())
    tmp = []
    for i in range(L, R + 1):
        tmp.append(i)
    id_list = list(set(id_list) & set(tmp))

print(len(id_list))


### FIXED CODE ###

N, M = map(int, input().split())

L, R = 1, N
for _ in range(M):
    Li, Ri = map(int, input().split())
    if L <= Li:
        L = Li
    if Ri <= R:
        R = Ri

print(R - L + 1 if (R >= L) else 0)
### BUGGY CODE ###

# atcoder DPまとめ
# D_Knapsack1

# def get_inputs():
#     [n, w] = [int(x) for x in input().split()]
#     g = []
#     for _ in range(n):
#         g.append([int(x) for x in input().split()])
#
#     return n, w, g


if __name__ == "__main__":
    
    n, w = map(int, input().split())
    
    #### First Try
    # この方法では後半の問題でTLEになってしまう
    # 二重ループの部分で時間がかかっている
    # # dp[i][w]はi-1個目の品物を加えるか吟味した後、重さw以下で最大の価値
    # dp = [[0] * (w + 1) for _ in range(n + 1)]
    #
    # for i in range(1, n + 1):
    #     for wgt in range(w + 1):
    #         if wgt >= g[i -1][0]:
    #             dp[i][wgt] = max(dp[i - 1][wgt - g[i - 1][0]] + g[i - 1][1], dp[i - 1][wgt])
    #         else:
    #             dp[i][wgt] = dp[i - 1][wgt]
    #
    # print(max(dp[n]))

    ### Second Try
    # 動的計画法の部分で、古いiの情報は不要で一つ前の状態さえあれば解ける
    # そこに着目し、かつ不要な判定や更新を減らすために、あるiの時に、
    # 大きなwから最適値を求めるようにする

    # dp[w]は,現在評価中のiにおいて、重さwの時の最大価値の値


    ### Third Try
    # maxをやめてif文に変更

    ### Fourth Try
    # 最初に荷物の情報をリストに読み込んでいたが、そこが時間がかかているようなので逐次読み込みに修正

    dp = [0] * (w + 1)      # 初期値は０　範囲は0〜wまで

    for i in range(n):      # 品物0からn-1までを評価
        wt, vl = map(int, input().split())
        for j in range(w, wt - 1, -1):
            tmp = dp[j - wt] + vl
            if tmp > dp[j]:
                dp[j] = tmp

    print((dp[w]))


### FIXED CODE ###

def calc(num,capacity):
    dp = [0]*(capacity+1)
    for _ in range(num):
        weight, value = map(int, input().split())
        for w in range(capacity,weight - 1,-1):
            tmp = dp[w - weight] + value
            if dp[w] < tmp:
              dp[w] = tmp
    return dp[capacity]
 
num, capacity = map(int, input().split())
print(calc(num,capacity))
### BUGGY CODE ###

N, M= (int(i) for i in input().split())

L = [0] * M
R = [0] * M

for i in range(M):
    L_tmp, R_tmp = map(int, input().split())
    L[i] = L_tmp
    R[i] = R_tmp

ans = []
for i in range(N):
  ans.append(i+1)

for i in range(M):
  ans = [j for j in ans if L[i]<=j and R[i]>=j]

print(len(ans))


### FIXED CODE ###

N, M= (int(i) for i in input().split())

L_max = 1
R_min = N

for i in range(M):
    L, R = map(int, input().split())
    L_max = max(L_max,L)
    R_min = min(R_min,R)

ans = set(range(L_max,R_min+1))

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

N,Q=[int(x) for x in input().split()]
S=list(input())

AC_list=[0]

for i in range(1,N):
  if (S[i-1]=='A')&(S[i]=='C'):
    AC_list.append(AC_list[i-1]+1)
  else:
    AC_list.append(AC_list[i-1])

for l in range(Q): 
  S,E=[int(x) for x in input().split()]
  
  print(max(AC_list[S-1:E])-min((AC_list[S-1:E])))

### FIXED CODE ###

N,Q=[int(x) for x in input().split()]
S=list(input())

t=[0]

for i in range(1,N):
  if (S[i-1]=='A')&(S[i]=='C'):
    t.append(t[i-1]+1)
  else:
    t.append(t[i-1])

for i in range(Q):
  r,l = map(int, input().split(" "))
  print(abs(t[r-1]-t[l-1]))
### BUGGY CODE ###

n = int(input())
s = input()
r, g, b = s.count('R'), s.count('G'), s.count('B')
cnt = r * g * b
for i in range(n):
    for j in range(i + 1, n):
        k = 2*j - i
        if j < k < n and len({s[i], s[j], s[k]}) == 3:
            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):
    for j in range(i + 1, n):
        k = 2*j - i
        if j < k < n and len({s[i], s[j], s[k]}) == 3:
            cnt -= 1
print(cnt)
### BUGGY CODE ###

def dist(p, q):
    return abs(p[0] - q[0]) + abs(p[1] - q[1])

n = int(input())
ans = 0
P = [tuple(map(int, input().split())) for _ in range(n)]
P.sort(key=lambda p: (p[0], p[1]))
ans = max(ans, max(dist(P[0], q) for q in P[1:]))
ans = max(ans, max(dist(P[-1], q) for q in P[:-1]))
P.sort(key=lambda p: (p[0], -p[1]))
ans = max(ans, max(dist(P[0], q) for q in P[1:]))
ans = max(ans, max(dist(P[-1], q) for q in P[:-1]))
P.sort(key=lambda p: (p[1], p[0]))
ans = max(ans, max(dist(P[0], q) for q in P[1:]))
ans = max(ans, max(dist(P[-1], q) for q in P[:-1]))
P.sort(key=lambda p: (p[1], -p[0]))
ans = max(ans, max(dist(P[0], q) for q in P[1:]))
ans = max(ans, max(dist(P[-1], q) for q in P[:-1]))

P.sort(key=lambda p: (-p[0], p[1]))
ans = max(ans, max(dist(P[0], q) for q in P[1:]))
ans = max(ans, max(dist(P[-1], q) for q in P[:-1]))
P.sort(key=lambda p: (-p[0], -p[1]))
ans = max(ans, max(dist(P[0], q) for q in P[1:]))
ans = max(ans, max(dist(P[-1], q) for q in P[:-1]))
P.sort(key=lambda p: (-p[1], p[0]))
ans = max(ans, max(dist(P[0], q) for q in P[1:]))
ans = max(ans, max(dist(P[-1], q) for q in P[:-1]))
P.sort(key=lambda p: (-p[1], -p[0]))
ans = max(ans, max(dist(P[0], q) for q in P[1:]))
ans = max(ans, max(dist(P[-1], q) for q in P[:-1]))
print(ans)

### FIXED CODE ###

def dist(p, q):
    return abs(p[0] - q[0]) + abs(p[1] - q[1])

n = int(input())
ans = 0
peri = []
P = [tuple(map(int, input().split())) for _ in range(n)]
P.sort(key=lambda p: (p[0], p[1]))
peri.append(max(P, key=lambda p: (p[0], p[1])))
peri.append(min(P, key=lambda p: (p[0], p[1])))
peri.append(max(P, key=lambda p: (p[0], -p[1])))
peri.append(min(P, key=lambda p: (p[0], -p[1])))
peri.append(max(P, key=lambda p: (-p[0], p[1])))
peri.append(min(P, key=lambda p: (-p[0], p[1])))
peri.append(max(P, key=lambda p: (-p[0], -p[1])))
peri.append(min(P, key=lambda p: (-p[0], -p[1])))
peri.append(max(P, key=lambda p: (p[1], p[0])))
peri.append(min(P, key=lambda p: (p[1], p[0])))
peri.append(max(P, key=lambda p: (-p[1], p[0])))
peri.append(min(P, key=lambda p: (-p[1], p[0])))
peri.append(max(P, key=lambda p: (p[1], -p[0])))
peri.append(min(P, key=lambda p: (p[1], -p[0])))
peri.append(max(P, key=lambda p: (-p[1], -p[0])))
peri.append(min(P, key=lambda p: (-p[1], -p[0])))
peri.append(max(P, key=lambda p: p[0]+p[1]))
peri.append(max(P, key=lambda p: -p[0]+p[1]))
peri.append(max(P, key=lambda p: p[0]-p[1]))
peri.append(max(P, key=lambda p: -p[0]-p[1]))

peri = set(peri)

for p in P:
    for q in peri:
        ans = max(ans, dist(p, q))
print(ans)
### BUGGY CODE ###

from collections import Counter
N,K = map(int,input().split())
tmp = Counter()
for i in range(N):
    a,b = map(int,input().split())
    tmp.update([a]*b)

print(sorted(tmp.elements())[K-1])

### FIXED CODE ###

n,k=[int(x) for x in input().split()]
s=[]
for i in [None]*n:
    a,b=[int(x) for x in input().split()]
    s.append((a,b))
s=sorted(s,key=lambda x : x[0])
for i in s:
    if i[1]>=k:
        print(i[0])
        break
    else:
        k-=i[1]
### BUGGY CODE ###

# -*-coding: utf-8 -*-
import numpy as np
def main():
    N = int(input())
    a = np.array(list(map(int, input().split())))
    a1 = a + 1
    a2 = a - 1
    lst = np.concatenate([a, a1, a2], 0)
    lst = list(lst)
    set_lst = list(set(lst))
    ans = 0
    for i in set_lst:
        tmp = lst.count(i)
        if tmp > ans:
            ans = tmp
    print(ans)
if __name__ == '__main__':
    main()

### FIXED CODE ###

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

cnt = [0] * 1000010
for i in a:
    cnt[i] += 1
    cnt[i+1] += 1
    cnt[i-1] += 1

print(max(cnt))
### BUGGY CODE ###

def binSearch(N, A, key):
    left = 0
    right = N - 1
    memo = [-1 for _ in range(N)]
    k = (left + right) // 2
    while True:
        if memo[k] == -1:
            memo[k] = 1 if key(A[k]) else 0
        if memo[k] == 1:
            right = k
        else:
            left = k
        _k = (left + right) // 2
        if _k == k:
            if memo[left] == -1:
                memo[left] = key(A[left])
            if memo[right] == -1:
                memo[right] = key(A[right])
            if memo[right] == 0 or memo[left] == 1:
                return -1
            else:
                return right
        else:
            k = _k


def trisum(n):
    return n * (n + 1) // 2


def calc(S):
    t = []
    i = S.find('><')
    while i != -1:
        t += [S[:i + 1]]
        S = S[i + 1:]
        i = S.find('><')
    t += [S]
    result = 0
    for u in t:
        nu = len(u)
        l = binSearch(nu, u, lambda c: c == '>')
        if l != -1:
            result += trisum(max(l, nu - l)) + trisum(min(l, nu - l) - 1)
        else:
            result += trisum(nu)
    return result


S = input()
print(calc(S))

### FIXED CODE ###

def binSearch(N, A, key):
    left = 0
    right = N - 1
    memo = [-1 for _ in range(N)]
    k = (left + right) // 2
    while True:
        if memo[k] == -1:
            memo[k] = 1 if key(A[k]) else 0
        if memo[k] == 1:
            right = k
        else:
            left = k
        _k = (left + right) // 2
        if _k == k:
            if memo[left] == -1:
                memo[left] = key(A[left])
            if memo[right] == -1:
                memo[right] = key(A[right])
            if memo[right] == 0 or memo[left] == 1:
                return -1
            else:
                return right
        else:
            k = _k


def trisum(n):
    return n * (n + 1) // 2


def calc(S):
    t = []
    b = 0
    i = S.find('><', b)
    result = 0
    while i != -1:
        if i - b == 0:
            result += 0
        elif i - b == 1:
            result += 1
        else:
            t += [S[b:i + 1]]
        b = i + 1
        i = S.find('><', b)
    t += [S[b:]]
    for u in t:
        nu = len(u)
        l = binSearch(nu, u, lambda c: c == '>')
        if l != -1:
            result += trisum(max(l, nu - l)) + trisum(min(l, nu - l) - 1)
        else:
            result += trisum(nu)
    return result


S = input()
print(calc(S))
### BUGGY CODE ###

from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
import sys

for line in sys.stdin:
    small, large = sorted(int(n) for n in line .split())
    for i in xrange(small, 0, -1):
        if large % i == 0 and small % i == 0:
            gcd = i
            break
    for i in xrange(2, large + 1):
        if i * small % large == 0:
            lcm = i * small
            break
    print(gcd, lcm)

### FIXED CODE ###

from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
import sys
from fractions import gcd

for line in sys.stdin:
    small, large = sorted(int(n) for n in line .split())
    G = gcd(large, small)
    print(G, large // G * small)
### BUGGY CODE ###

n = int(input())
v = [int(i) for i in input().split()]
ans = 1
for l in v:
    ans *= l;

if ans > 1e18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import math
import itertools
import functools
import numpy as np



# a, b = map(float, input().split())

# b = int(b * 100)
# a = int(a)

# print(int(a * b / 100))

n = int(input())
v = [int(i) for i in input().split()]
v.sort()

if v[0] == 0:
  print(0)
  exit(0)
ans = 1
for l in v:
    ans *= l
    if ans > 1e18:
      print(-1)
      exit(0)
 
if ans > 1e18:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

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

max_scope_list = []
for p_i in range(len(p_list)):

    now_scope_list = []
    for i in range(k):
        if len(p_list) <= (p_i + i):
            break
        now_scope_list.append(p_list[p_i + i])

    if sum(max_scope_list) < sum(now_scope_list):
        max_scope_list = now_scope_list

ex = 0
for scope in max_scope_list:
    dice = [r for r in range(1, scope+1)]
    p = 1/len(dice)
    for d in dice:
        ex += p*d
print(ex)


### FIXED CODE ###

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

scope_index = 0
max_sum = 0
for i in range(k):
    max_sum += p_list[i]

now_sum = max_sum
for p_i in range(k, len(p_list)):
    now_sum -= p_list[p_i - k]
    now_sum += p_list[p_i]

    if max_sum < now_sum:
        scope_index = p_i
        max_sum = now_sum

ex = (max_sum+k)/2
print(ex)
### BUGGY CODE ###

from bisect import*
def main():
    root=[[],[]]
    def search_higher(key):
        ptr0,ptr1=root
        ret=None
        while ptr1:
            i=bisect(ptr0,key)
            if i!=len(ptr0):ret=ptr0[i]
            ptr0,ptr1=ptr1[i]
        i=bisect(ptr0,key)
        if i!=len(ptr0):ret=ptr0[i]
        return ret
    def search_lower(key):
        ptr0,ptr1=root
        ret=None
        while ptr1:
            i=bisect_left(ptr0,key)
            if i!=0:ret=ptr0[i-1]
            ptr0,ptr1=ptr1[i]
        i=bisect_left(ptr0,key)
        if i!=0:ret=ptr0[i-1]
        return ret
    def insert_rec(ptr,key):
        ptr0,ptr1=ptr
        b_size=64
        if not ptr[1]:
            insort(ptr0,key)
            if len(ptr0)==b_size*2-1:
                ret=[ptr0[:b_size],[]]
                ptr[0]=ptr0[b_size:]
                return ret
        else:
            i=bisect(ptr0,key)
            tmp=insert_rec(ptr1[i],key)
            if tmp:
                ptr0.insert(i,tmp[0].pop())
                ptr1.insert(i,tmp)
                if len(ptr1)==b_size*2:
                    ret=[ptr0[:b_size],ptr1[:b_size]]
                    ptr[0],ptr[1]=ptr0[b_size:],ptr1[b_size:]
                    return ret
    def insert(key):
        tmp=insert_rec(root,key)
        if tmp:root[0],root[1]=[tmp[0].pop()],[tmp,root]
    n,*a=map(int,open(0).read().split())
    l=[0]*n
    for i,v in enumerate(a,1):l[v-1]=i
    insert(0)
    insert(n+1)
    c=0
    for i,v in enumerate(l,1):
        c+=(search_higher(v)-v)*(v-search_lower(v))*i
        insert(v)
    print(c)
main()

### FIXED CODE ###

root=lambda x:x if par[x]==x else root(par[x])
same=lambda x,y:root(x)==root(y)
def unite(*z):
  x,y=map(root,z)
  if x!=y:
    if rank[x]<rank[y]:
      par[x]=y
      size[y]+=size[x]
    else:
      par[y]=x
      size[x]+=size[y]
      if rank[x]==rank[y]:rank[x]+=1
n,*a=map(int,open(0).read().split())
*par,=range(n)
rank=[1]*n
size=[1]*n
b=[0]*n
for i,t in enumerate(a):b[t-1]=i
c=0
for k in b[::-1]:
  l=r=1
  if k>0 and a[k-1]>a[k]:
    l+=size[root(k-1)]
    unite(k-1,k)
  if k+1<n and a[k+1]>a[k]:
    r+=size[root(k+1)]
    unite(k+1,k)
  c+=l*r*a[k]
print(c)
### BUGGY CODE ###

N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
F = sorted(list(map(int, input().split())), reverse=True)


# にぶたん := N人のメンバーそれぞれが完食にかかる時間のうち最大値をxに以下にできるか？
ok, ng = 10 ** 12 + 1, -1
while ok - ng > 1:
    x = (ok + ng) // 2

    need_training = 0
    for a, f in zip(A, F):
        need_training += max(0, a - x // f)

        if need_training > K:
            ng = x
            break
    else:
        ok = x

print(ok)


### FIXED CODE ###

from math import ceil
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
F = sorted(list(map(int, input().split())), reverse=True)

K = min(K, sum(A))
X = [[a, f] for a, f in zip(A, F)]

ok, ng = 10 ** 12 + 1, -1
while abs(ok - ng) > 1:
    m = (ok + ng) // 2
    k_cost = 0
    for a, f in X:
        if a * f <= m:
            continue
        else:
            k_cost += max(0, ceil(-(m / f - a)))

    if k_cost <= K:
        ok = m
    else:
        ng = m

print(ok)
### BUGGY CODE ###

#
# author Sidratul
#

from math import prod

if __name__ == '__main__':
    n = input()
    a = list(map(int, input().split(' ')))
    s = prod(a)
    if s > 10**18:
        print(-1)
    else:
        print(s)

### FIXED CODE ###

#
# author Sidratul
#

from math import prod

if __name__ == '__main__':
    n = input()
    a = list(map(int, input().split(' ')))
    s = 1
    a.sort()
    x = True
    for i in range(len(a)):
        s = s * a[i]
        if s > 10**18:
            print(-1)
            x = False
            break
    if x:
        print(s)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
import math

k = int(input())
ret = 0
for i in range(1, k+1):
    for j in range(1, k+1):
        for k in range(1, k+1):
            ret += math.gcd(math.gcd(i, j), k)
print(ret)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
try:
    from math import gcd
except:
    from fractions import gcd

k = int(input())

memo = [[0] * 201 for _ in range(201)]
for i in range(201):
    for j in range(201):
        memo[i][j] = gcd(i, j)
ret = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            val = memo[a][b]
            ret += memo[val][c]
print(ret)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
ACs_indices = [i for i in range(N-1) if S[i:i+2] == 'AC']

for _ in range(Q):
    l, r = map(int, input().split())
    ans = 0
    for idx in ACs_indices:
        if idx in range(l-1, r-1):
            ans += 1
    print(ans)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
cum_sum = [0]*(N+1)
for i in range(2, N+1):
    if S[i-2:i] == 'AC':
        cum_sum[i] = cum_sum[i-1] + 1
    else:
        cum_sum[i] = cum_sum[i-1]

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

N, M = map(int, input().split())
G = [[] for _ in range(N)]

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

for g in G[N - 1]:
    if g in G[0]:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")


### FIXED CODE ###

N, M = map(int, input().split())
G = [set() for i in range(N + 1)]

for i in range(M):
    a, b = map(int, input().split())
    G[a].add(b)
    G[b].add(a)

for a in G[1]:
    if a in G[N]:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")
### BUGGY CODE ###

n = int(input())

kami = []

for i in range(n) :
    a = int(input())
    if a in kami :
        kami.remove(a)
    else :
        kami.append(a)

print(len(kami))


### FIXED CODE ###

n = int(input())
kami = set()

for i in range(n) :
    a = int(input())
    if a in kami :
        kami.remove(a)
    else :
        kami.add(a)

print(len(kami))
### BUGGY CODE ###

X=input()
a=list()
for i in range(len(X)):
    a.append(int(X[i:len(X)])%2019)
S=a.count(0)    
for j in set(a):
    b=a.count(j)
    S+=int(b*(b-1)/2)
print(S)



### FIXED CODE ###

A=[0]*2019
s=input()
a=0
b=1
for i in range(len(s)):
    b=b%2019
    a=(a+int(s[len(s)-1-i])*b)%2019
    b=b*10
    A[a]+=1
x=A[0]
for j in range(2019):
    x+=int(A[j]*(A[j]-1)/2)
print(x)
### BUGGY CODE ###

N = int(input())
A = input().split()
A = [int(n) for n in A]
for i in range(N):
  count = 0
  for j in range(N-1):
    if i+1 == A[j]:
      count += 1
  print(count)


### FIXED CODE ###

N = int(input())
A =[int(n) for n in input().split()]
b = [0]*N
for i in A:
  b[i-1]+=1
for i in range(N):
  print(b[i])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
b = [0 for _ in range(q)]
c = [0 for _ in range(q)]
for i in range(q):
    b[i], c[i] = map(int, input().split())

for num, rep in zip(b, c):
    if num in set(a):
        a = [rep if ele == num else ele for ele in a]
        print(sum(a))
    else:
        print(sum(a))
        continue

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
X = Counter(a)
q = int(input())
b = [0 for _ in range(q)]
c = [0 for _ in range(q)]
for i in range(q):
    b[i], c[i] = map(int, input().split())

ans = sum(a)
for num, rep in zip(b, c):
    ans += (rep * X[num] - num * X[num])
    X[rep] += X[num]
    del(X[num])
    print(ans)
### BUGGY CODE ###

#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n,k = readInts()
A = readInts()
res = [0] * (n-k+1)
pa = 1
for i in range(k):
    pa *= A[i]
res[0] = pa
for i in range(1,n-k+1):
    res[i] = res[i-1] * A[i+k-1] // A[i-1]
#print(res)
for i in range(1,n-k+1):
    if res[i-1] < res[i]:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n,k = readInts()
A = readInts()
for i in range(n-k):
    if A[i] < A[i+k]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n = int(input())
s = input()

max_count = 0
for i in range(n):
    for j in range(n):
        if i >= j:
            continue
        if s[i] == s[j]:
            count = 1
            while True:
                if i+count <= j and s[i:i+count] == s[j:j+count]:
                    #print(count, i, s[i:i+count])
                    count += 1
                else:
                    max_count = max(max_count, count-1)
                    break
print(max_count)

### FIXED CODE ###

tmp = input()
my_str = input()
 
start = 0
end = 1
max_len = 0
 
while (end < len(my_str)):
    if my_str[start:end] in my_str[end:]:
        if end - start > max_len:
            max_len = end - start
        end += 1
    else:
        start += 1
print(max_len)