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

import bisect
n,d,a= map(int, input().split())
x= [list(map(int, input().split())) for i in range(n)]

x.sort()
y=[]
for i in range(n):
    y.append(x[i][0])
    x[i][1]=-(-x[i][1]//a)

# どのモンスターまで倒したか管理しながら進める。
ans=0
for i in range(n):
    if x[i][1]>=1:
        w=x[i][1]
        ans+=w
        q=bisect.bisect_right(y,x[i][0]+2*d)
        for j in range(q-i):
            x[i+j][1]-=w
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
import bisect
import collections
from collections import deque
n,d,a= map(int, input().split())
x= [list(map(int, input().split())) for i in range(n)]

x.sort()
y=[]
for i in range(n):
    y.append(x[i][0])
    x[i][1]=-(-x[i][1]//a)

# どのモンスターまで倒したか管理しながら進める。
# 累積ダメージを管理
qq=deque([])
ans=0
atk=0
for i in range(n):
    w=x[i][1]
    # iがダメージの有効期限を超過している場合
    while len(qq)>0 and i > qq[0][0]:
        atk-=qq[0][1]
        qq.popleft()

    if w-atk>0:
        ans+=w-atk
        q=bisect.bisect_right(y,x[i][0]+2*d)-1
        # 有効期限　ダメージ
        qq.append([q,w-atk])
        atk += w - atk
print(ans)
### BUGGY CODE ###

def main():
    import sys
    sys.setrecursionlimit(10**6)
    mod = 10**9+7
    
    fact = [1,1]
    finv = [1,1]
    inv = [0,1]
    
    for i in range(2,2*10**5+5):
        fact.append((fact[-1]*i)%mod)
        inv.append((inv[mod%i]*(mod-mod//i))%mod)
        finv.append((finv[-1]*inv[-1])%mod)
    
    def nCr(n,r,mod):
        
        return fact[n]*finv[r]*finv[n-r]%mod

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

    numl = [0]*n
    resl = [0]*n
    def dfs(x,pre):
        num = 0
        res = 1
        for nex in e[x]:
            if nex == pre:
                continue
            dfs(nex,x)
            num += numl[nex]
            res *= nCr(num,numl[nex],mod)*resl[nex]
            res %= mod
        numl[x] = num+1
        resl[x] = res

        return 

    dfs(0,-1)

    ans = [0]*n
    ans[0] = resl[0]
    def dfs2(x,pre):
        
        for nex in e[x]:
            if nex == pre:
                continue
            pres = [resl[x], numl[x], resl[nex], numl[nex]]
            resl[x] *= pow(nCr(numl[x]-1,numl[nex],mod)*resl[nex],mod-2,mod)
            resl[x] %= mod
            numl[x] -= numl[nex]
            resl[nex] *=  nCr(numl[x]+numl[nex]-1,numl[x],mod)*resl[x]
            resl[nex] %= mod
            numl[nex] += numl[x]
            ans[nex] = resl[nex]
            dfs2(nex,x)
            resl[x], numl[x], resl[nex], numl[nex] = pres
        return
    dfs2(0,-1)
    for i in ans:
        print(i)
if __name__ == "__main__":
    main()

### FIXED CODE ###


import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
mod = 10**9+7
 
fact = [1,1]
finv = [1,1]
inv = [0,1]
 
for i in range(2,2*10**5+5):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)
 
def nCr(n,r,mod):
      
    return (fact[n]*finv[r])%mod*finv[n-r]%mod

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

numl = [0]*n
resl = [0]*n
def dfs(x,pre):
    num = 0
    res = 1
    for nex in e[x]:
        if nex == pre:
            continue
        dfs(nex,x)
        num += numl[nex]
        res *= nCr(num,numl[nex],mod)*resl[nex]
        res %= mod
    numl[x] = num+1
    resl[x] = res

    return 

dfs(0,-1)

ans = [0]*n
ans[0] = resl[0]
def dfs2(x,pre):
    
    for nex in e[x]:
        if nex == pre:
            continue
        pres = [resl[x], numl[x], resl[nex], numl[nex]]
        resl[x] *= pow(nCr(numl[x]-1,numl[nex],mod)*resl[nex],mod-2,mod)
        resl[x] %= mod
        numl[x] -= numl[nex]
        resl[nex] *=  nCr(numl[x]+numl[nex]-1,numl[x],mod)*resl[x]
        resl[nex] %= mod
        numl[nex] += numl[x]
        ans[nex] = resl[nex]
        dfs2(nex,x)
        resl[x], numl[x], resl[nex], numl[nex] = pres
    return
dfs2(0,-1)
for i in ans:
    print(i)
### BUGGY CODE ###

n = int(input())
num = [ int(input()) for _ in range(n) ]
for i in range(n):
    print(max(num[0:i]+num[i+1:]))

### FIXED CODE ###

n = int(input())
num = [ int(input()) for _ in range(n) ]
B = sorted(num,reverse=True)
maxnum = B[0]
maxnum2 = B[1]

for i in range(n):
    if num[i] != maxnum:
        print(maxnum)
    else:
        print(maxnum2)
### BUGGY CODE ###

def Eratosthenes(n):
	N = {i:True for i in range(2,n+1)}
	primeNumbers = []
	for i in range(2,n+1):
		if N[i]:
			primeNumbers.append(i)
			j = i*2
			while j<=n:
				N.update({j:False})
				j += i
	return primeNumbers

while True:
	try:
		n = int(input())
		print(len(Eratosthenes(n)))
	except EOFError:
		break

### FIXED CODE ###

def Eratosthenes(n):
	N = [1 for i in range(0,n+1)]
	i = 3
	while i*i<=n:
		if N[i]:
			j = i*i
			while j<=n:
				N[j] = 0
				j += i*2
		i += 2
	return N

N = Eratosthenes(999999)
while True:
	try:
		n = int(input())
	except EOFError:
		break
	cnt = 0
	if n>=2:
		cnt = 1
	for i in range(3, n+1, 2):
		cnt += N[i]
	print(cnt)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

import heapq

INF = 10 ** 10

class Edge():
    def __init__(self, end, cost):
        self.end = end
        self.cost = cost

def dijkstra(n, G, s):
    dist = [INF] * n
    dist[s] = 0
    h = []
    heapq.heappush(h, (0, s))

    while h:
        # 使っていない頂点のうち、現時点で最も距離の近いものを選びvとする
        d, v = heapq.heappop(h)
        if dist[v] < d:
            continue
        # vから到達可能な頂点について、距離が短くなれば更新
        for e in G[v]:
            if dist[e.end] > dist[v] + e.cost:
                dist[e.end] = dist[v] + e.cost
                heapq.heappush(h, (dist[e.end], e.end))
    return dist


H, W = map(int, input().split())
N = H * W
ch, cw = map(lambda x:int(x)-1, input().split())
gh, gw = map(lambda x:int(x)-1, input().split())

s = []
es = tuple([] for i in range(N))

for h in range(H):
   s.append(input().rstrip('\n'))

for h in range(H):
    for w in range(W):
        if s[h][w] != '.':
            continue
        a = h*W+w
        esappend = es[a].append
        for dh in (-2, -1, 0, 1, 2):
            for dw in (-2, -1, 0, 1, 2):
                if dh == 0 and dw == 0:
                    continue
                nh = h + dh
                nw = w + dw
                if 0 <= nh and nh < H and 0 <= nw and nw < W and s[nh][nw] == '.':
                    b = nh*W+nw
                    if (dh, dw) in [(-1,0),(1,0),(0,-1),(0,1)]:
                        esappend(Edge(b, 0))
                    else:
                        esappend(Edge(b, 1))

dist = dijkstra(N, es, ch*W+cw)
if dist[gh*W+gw] == INF:
    print(-1)
else:
    print(dist[gh*W+gw])

### FIXED CODE ###

import sys
input = sys.stdin.readline

import heapq

INF = 10 ** 10

def dijkstra(n, G, s):
    dist = [INF] * n
    dist[s] = 0
    h = []
    heapq.heappush(h, (0, s))

    while h:
        # 使っていない頂点のうち、現時点で最も距離の近いものを選びvとする
        d, v = heapq.heappop(h)
        if dist[v] < d:
            continue
        # vから到達可能な頂点について、距離が短くなれば更新
        for end, cost in G[v]:
            if dist[end] > dist[v] + cost:
                dist[end] = dist[v] + cost
                heapq.heappush(h, (dist[end], end))
    return dist


H, W = map(int, input().split())
N = H * W
ch, cw = map(lambda x:int(x)-1, input().split())
gh, gw = map(lambda x:int(x)-1, input().split())

s = []
es = tuple([] for i in range(N))

for h in range(H):
   s.append(input().rstrip('\n'))

for h in range(H):
    for w in range(W):
        if s[h][w] != '.':
            continue
        a = h*W+w
        esappend = es[a].append
        for dh in (-2, -1, 0, 1, 2):
            for dw in (-2, -1, 0, 1, 2):
                if dh == 0 and dw == 0:
                    continue
                nh = h + dh
                nw = w + dw
                if 0 <= nh and nh < H and 0 <= nw and nw < W and s[nh][nw] == '.':
                    b = nh*W+nw
                    if (dh, dw) in [(-1,0),(1,0),(0,-1),(0,1)]:
                        esappend((b, 0))
                    else:
                        esappend((b, 1))

dist = dijkstra(N, es, ch*W+cw)
if dist[gh*W+gw] == INF:
    print(-1)
else:
    print(dist[gh*W+gw])
### BUGGY CODE ###

#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from heapq import heappush, heappop

def resolve():
    it = map(int, sys.stdin.read().split())
    N, M, K = next(it), next(it), next(it)
    A = [next(it) for i in range(N)]
    B = [next(it) for i in range(M)]

    dq = []
    heappush(dq, (0, 0, 0, 0))
    ans = 0
    while dq:
        k, n, i, j = heappop(dq)

        if k > K:
            break
        ans = max(ans, n)

        if i < N:
            heappush(dq, (k+A[i], n+1, i+1, j))
        if j < M:
            heappush(dq, (k+B[j], n+1, i, j+1))

    print(ans)


if __name__ == "__main__":
    resolve()


### FIXED CODE ###

#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    N, M, K = next(it), next(it), next(it)

    A = [0] * (N+1)
    B = [0] * (M+1)
    ans = 0
    for i in range(1, N+1):
        A[i] = A[i-1] + next(it)
    for i in range(1, M+1):
        B[i] = B[i-1] + next(it)

    lo = 0
    hi = 2*(N+M)+1
    while lo < hi:
        mid = (lo+hi)//2
        for j in range(max(0, mid-M), min(mid, N)+1):
            if A[j] + B[mid-j] <= K:
                lo = mid+1
                break
        else:
            hi = mid

    print(lo-1)


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

def resolve():
    import itertools
    N, K = [int(i) for i in input().split()]
    A = [int(i) for i in input().split()]
    minA = 10**9
    for a in itertools.combinations(A, K):
        minA = min(minA, sum(a))
    print(minA)

resolve()


### FIXED CODE ###

def resolve():
    N, K = [int(i) for i in input().split()]
    A = sorted([int(i) for i in input().split()])
    sumA = 0
    for a in A[:K]:
        sumA += a
    print(sumA)


resolve()
### BUGGY CODE ###

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


# 入力を整数に変換して受け取る
def input_int():
    return int(input())


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    n, k = input_to_int_map()
    a_array = input_to_int_tuple()

    temp = [1]
    val = 1
    for a in a_array:
        val *= a
        temp.append(val)

    for i in range(k + 1, n + 1):
        k_val = temp[i]
        ini_k_val = temp[i - k]
        pre_k_val = temp[i - 1]
        ini_pre_k_val = temp[i - 1 - k]
        k_val /= ini_k_val
        pre_k_val /= ini_pre_k_val

        if pre_k_val < k_val:
            print("Yes")
        else:
            print("No")


if __name__ == "__main__":
    main()


### FIXED CODE ###

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


# 入力を整数に変換して受け取る
def input_int():
    return int(input())


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    n, k = input_to_int_map()
    a_array = input_to_int_tuple()

    for k_val, pre_k_val in zip(a_array[k:], a_array[k - k:]):
        if k_val > pre_k_val:
            print("Yes")
        else:
            print("No")

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

def main():
    n = int(input())
    a = list(map(int, input().split()))
    b = sorted(a)
    for i in range(n):
        j = b.index(a[i])
        c = b[:j] + b[j+1:]
        print(c[n // 2 - 1])

        
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    b = sorted(a)
    
    for i in range(n):
        if a[i] <=  b[n // 2 - 1]:
            print(b[n // 2])
        elif a[i] >  b[n // 2 - 1]:
            print(b[n // 2 - 1])
        
        
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
q = int(input())
B = []
C = []
D = []
for i in range(q):
    ans = 0
    b, c = map(int, input().split())
    for j in range(len(A)):
        if A[j] == b:
            A[j] = c
            ans += c
        else:
            ans += A[j]
    print(ans)


### FIXED CODE ###

from collections import Counter
n = int(input())
A = list(map(int, input().split()))
q = int(input())

ans = sum(A)
dic = Counter(A)
for i in range(q):
    b, c = map(int, input().split())
    cnt = dic[b]
    dic[b] = 0
    dic[c] += cnt
    ans -= cnt*b
    ans += cnt*c
    print(ans)
### BUGGY CODE ###

def main():

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

    for i in range(K):
        if A >= 1:
            A -= 1
        elif B >= 1:
            B -= 1

    print(str(A) + " " + str(B))


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():

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

    if A > K:
        A -= K
    else:

        K -= A
        A = 0
        B -= K
        if B <= 0:
            print("0 0")
            exit(0)

    print(str(A) + " " + str(B))


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

import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
n,q=[int(_) for _ in input().split()]
ki=[[] for _ in range(n)]
ans=[0]*n
 
def dfs(numQ):
    for child in ki[numQ]:
        ans[child]+=ans[numQ]
        dfs(child)
 
for i in range(n-1):
    a,b=[int(_) for _ in input().split()]
    ki[a-1].append(b-1)
    ki[b-1].append(a-1)
 
for i in range(q):
    p,x=[int(_) for _ in input().split()]
    ans[p-1]+=x
 
dfs(0)
print(*ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
n,q=[int(_) for _ in input().split()]
ki=[[] for _ in range(n)]
ans=[0]*n
 
def dfs(numQ,parent):
    for child in ki[numQ]:
        if child==parent:
            continue
        ans[child]+=ans[numQ]
        dfs(child,numQ)
 
for i in range(n-1):
    a,b=[int(_) for _ in input().split()]
    ki[a-1].append(b-1)
    ki[b-1].append(a-1)
 
for i in range(q):
    p,x=[int(_) for _ in input().split()]
    ans[p-1]+=x
 
dfs(0,-1)
print(*ans)
### BUGGY CODE ###

value = 0
N = int(input())
L = list(map(int,input().split()))
L = sorted(L)  

for i in range(N-2):
  for j in range(i+1,N-1):
    x = L[i]+L[j]
    B = N-1
    A = j
    max_c_index = j
 #   while True:
    while A <= B: #A>Bとなったときに停めるようにすれば簡潔
     # M = A + (B-A)//2
      M = (A+B)//2 #こう書くほうがシンプル
      if L[M] < x:
        max_c_index = M
        A = M+1
      else:
#        B = M
        B = M-1
    value += max_c_index - j
print(value)

### FIXED CODE ###

from bisect import bisect_left
N = int(input())
L = sorted(list(map(int, input().split())))

ans = 0
for i in range(N):  # １番短い棒
    for j in range(i + 1, N):  # 真ん中の長さの棒
        ans += bisect_left(L, L[i] + L[j]) - (j + 1)

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

def main():
    N = int(input())
    G = [[] for i in range(N + 1)]
    for i in range(N-1):
        u, v, w = (int(i) for i in input().split())
        G[u].append((v,w))
        G[v].append((u,w))
    def is_bipartite_by_dfs(G,v,color):
        todo = []
        cur = 0
        color[v] = cur
        todo.append(v)
        while todo:
            u = todo[-1]
            for next_v,w in G[u]:
                if color[next_v] != -1: 
                    continue
                if w&1:
                    color[next_v] = (color[u] + 1) % 2
                else:
                    color[next_v] = color[u]
                todo.append(next_v)
                break
            else:
                todo.pop()
    color = [-1] * (N + 1) # 0: white, 1: black, -1: undefined
    is_bipartite_by_dfs(G,1,color)
    for i in range(1,N+1):
        print(color[i])
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    G = [[] for _ in range(N+1)]
    st = 0
    st_w = 0
    for i in range(N-1):
        u, v, w = (int(i) for i in input().split())
        G[u].append((v, w))
        G[v].append((u, w))
        if i == 0:
            st = u
            st_w = w
    color = [-1] * (N+1)  # 0: white, 1: black, -1: undefined
    from collections import deque

    def coloring(v, w):
        """
        breadth-first search
        a simplified version
        """
        que = deque()
        color[v] = 0
        que.append((v, w))
        while que:
            u, w = que.popleft()
            for v, d in G[u]:
                if color[v] != -1:
                    continue
                if d % 2 != 0:
                    n_col = (color[u] + 1) % 2
                else:
                    n_col = color[u]
                color[v] = n_col
                que.append((v, d))

    coloring(st, st_w)
    for c in color[1:]:
        print(c)


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

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

a = m//n

for i in range(1, a+1)[::-1]:
    if m%i == 0:
        break

print(i)

### FIXED CODE ###

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

a = m//n

for i in range(1, a+1)[::-1]:
    if m%i == 0:
        break

print(i)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
scores = []
for i in range(k-1, n):
  score = 1
  for j in range(i-k+1, i+1):
    score *= a[j]
  scores.append(score)
for i in range(1, len(scores)):
  if scores[i] > scores[i-1]:
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
pre_score = 1
for i in range(k, n):
  after_score = pre_score*a[i]/a[i-k]
  if after_score > pre_score:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

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

x, y, z, k = map(int, input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

yam = []
for l in range(x):
    for m in range(y):
        for n in range(z):
            yam.append(a[l]+b[m]+c[n])
yam.sort(reverse=True)
#print(yam)

for l in range(k):
        print(yam[l])

### FIXED CODE ###

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

import heapq

x, y, z, k = map(int, input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

yam = []
for l in range(x):
    for m in range(y):
        for n in range(z):
            if k < len(yam) and a[l]+b[m]+c[n] <= yam[0]:
                break
            elif k < len(yam):
                heapq.heappushpop(yam, a[l]+b[m]+c[n])
            else:
                heapq.heappush(yam, a[l]+b[m]+c[n])
yam.sort(reverse=True)
#print(yam)

for l in range(k):
        print(yam[l])
### BUGGY CODE ###

s = input()
n = len(s)
old_length=-1
for i in range(n):
  if old_length==len(s):
    break
  old_length=len(s)
  s=s.replace('0101','').replace('1010','').replace('01','').replace('10','')
print(n-len(s))

### FIXED CODE ###

s = input()
c1,c2=s.count('0'),s.count('1'),
print(min(c1,c2)*2)
### BUGGY CODE ###

s = input()
t = input()

ls,lt = len(s),len(t)
if ls > lt:
    #短い方をsに固定
    s,t = t,s
    ls,lt = lt,ls
dp=[("",0,0)]
common_str_set = set([""])
max_len = 0
i_ans = 0
for i,c in enumerate(s):
    for common_str,j,l_dp in dp.copy():
        for k,ct in enumerate(t[j:],j):
            if c == ct and (common_str+c) not in common_str_set:
                dp.append((common_str+c,k+1,l_dp+1))
                common_str_set.add(common_str+c)
                if l_dp+1 > max_len:
                    max_len = l_dp+1
                    i_ans = len(dp)-1
print(dp[i_ans][0])

### FIXED CODE ###

s = input()
t = input()

ls,lt = len(s),len(t)
dp = [[0]*(lt+1) for _ in [0]*(ls+1)]

for i,cs in enumerate(s,1):
    for j,ct in enumerate(t,1):
        if cs==ct:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])

i = ls
j = lt
ans = ""
while i>0 and j>0:
    if s[i-1] == t[j-1]:
        ans += s[i-1]
        i -= 1
        j -= 1
    else:
        if dp[i-1][j] > dp[i][j-1]:
            i -=1
        else:
            j -=1
print(ans[::-1])
### BUGGY CODE ###

import bisect
from collections import deque
N = int(input())
A = deque([])
for i in range(N):
  A.append(int(input()))

ans = 0
while len(A) > 0:
  dp = []
  l = len(A)
  for _ in range(l):
    a = A.popleft()
    if len(dp)==0:
      dp.append(a)
    elif a > dp[-1]:
      dp.append(a)
    else:
      pos = bisect.bisect_left(dp, a)
      A.append(dp[pos])
      dp[pos] = a
  ans += 1

print(ans)

### FIXED CODE ###

import bisect
from collections import deque
N = int(input())
A = deque([])
for i in range(N):
  A.append(int(input()))

dp = deque([])
l = len(A)
for i,a in enumerate(A):
  pos = bisect.bisect_left(dp, a)-1
  if pos<0:
    dp.appendleft(a)
  else:
    dp[pos] = a

print(len(dp))
### BUGGY CODE ###

from collections import Counter, defaultdict

def update(dic, b, c):
    dic = dic.copy()
    n = dic.pop(b)
    dic[c] += n
    return dic

def calc_diff(dic, b, c):
    return c * dic[b] - b * dic[b]

def calc_total(dic):
    return sum(k * v for k, v in dic.items())

N = int(input())
lis = list(map(int, input().split()))
dic = defaultdict(int)
dic.update(Counter(lis))
Q = int(input())
total = calc_total(dic)
for _ in range(Q):
    B, C = map(int, input().split())
    total += calc_diff(dic, B, C)
    print(total)
    dic = update(dic, B, C)

### FIXED CODE ###

from collections import Counter

def update(dic, b, c):
    n = dic.pop(b)
    dic[c] = n + dic.get(c, 0)
    
def calc_diff(dic, b, c):
    if dic.get(b):
        return c * dic[b] - b * dic[b]
    return 0

def calc_total(dic):
    return sum(k * v for k, v in dic.items())

N = int(input())
lis = list(map(int, input().split()))
dic = dict(Counter(lis))
Q = int(input())
total = calc_total(dic)
for _ in range(Q):
    B, C = map(int, input().split())
    diff = calc_diff(dic, B, C)
    total += diff
    print(total)
    if diff:
        update(dic, B, C)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
for i in range(1, N + 1):
    print(A.count(i))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
li = []
for i in range(n):
    li.append(0)
for x in a:
    li[x-1] += 1
for s in li:
    print(s)