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

#Solve this by Rerooting
import sys
from itertools import accumulate
import queue
input = sys.stdin.buffer.readline

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


#bfs、直すの面倒なので読み替えて。
dfs_order = []
parent = [-1] * N
root = 0
#queue
stack = queue.Queue()
stack.put(root)
while not stack.empty():
    node = stack.get()
    dfs_order.append(node)
    for next_node in adj[node]:
        if next_node != parent[node]:
            parent[next_node] = node
            stack.put(next_node)

dp1 = [1] * N
for node in reversed(dfs_order):
    for next_node in adj[node]:
        if next_node != parent[node]:
            dp1[node] = max(dp1[node], dp1[next_node] + 1)

dp2 = [1] * N
for node in dfs_order:
    around = [dp1[next_node]+1 if next_node != parent[node] else dp2[node] for next_node in adj[node]]
    from_left = [1] + list(accumulate(around, max))[:-1]
    from_right = list(accumulate(reversed(around), max))[-2::-1] + [1]
    without = [max(l, r) + 1 for l, r in zip(from_left, from_right)]
    for next_node, value in zip(adj[node], without):
        if next_node != parent[node]:
            dp2[next_node] = value

dp = [v1 + v2 - 1 for v1, v2 in zip(dp1, dp2)]

length = max(dp)

if length % 3 == 2:
    print("Second")
else:
    print("First")


### FIXED CODE ###

import sys
import queue

input = sys.stdin.buffer.readline
INF = 10 ** 9

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

#find the longest path by trying BFS twice.
q = queue.Queue()
depth = [INF] * N
q.put(0)
depth[0] = 1
while not q.empty():
    node = q.get()
    for next_node in path[node]:
        if depth[next_node] > depth[node] + 1:
            depth[next_node] = depth[node] + 1
            q.put(next_node)

#The 'node' gives one end of the longest path.
q = queue.Queue()
depth = [INF] * N
q.put(node)
depth[node] = 1
while not q.empty():
    node = q.get()
    for next_node in path[node]:
        if depth[next_node] > depth[node] + 1:
            depth[next_node] = depth[node] + 1
            q.put(next_node)

length = depth[node]

if length % 3 == 2:
    print("Second")
else:
    print("First")
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
total_breaks = 0
position = 0
for i in range(1, n + 1):
    try:
        breaks = a[position::].index(i)
        total_breaks += breaks
        position = position + breaks + 1
    except ValueError:
        if position == 0:
            total_breaks = -1
            break
        else:
            total_breaks = total_breaks + n - position
            break
print(total_breaks)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
total_breaks = 0
position = 0
for i in range(1, n + 1):
    try:
        next_position = a.index(i, position)
        if next_position < position:
            total_breaks = total_breaks + n - position
            break
        total_breaks = total_breaks + next_position - position
        position = next_position + 1
    except ValueError:
        if position == 0:
            total_breaks = -1
            break
        else:
            total_breaks = total_breaks + n - position
            break
print(total_breaks)
### BUGGY CODE ###

import sys
a,b = map(int,input().split())
base = 1
if a > 0 and b > 0:
    print('Positive')
    sys.exit()
for i in range(a,b+1):
    if i == 0:
        print('Zero')
        sys.exit()
    base = base * i
if base > 0:
    print('Positive')
elif base < 0:
    print('Negative')

### FIXED CODE ###

import sys
a,b = map(int,input().split())
if a > 0:
    print('Positive')
    sys.exit()
if b >= 0:
    print('Zero')
    sys.exit()
if (b-a+1)%2 == 1:
    print('Negative')
else:
    print('Positive')
### BUGGY CODE ###

from heapq import heappop, heappush
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

g = [[10**10 for _ in range(n)] for __ in range(n)]

flag = [0]*n  # flag[i]:i←i+1 に0のパスがある(0<=i<=n-1)

for _ in range(m):
    l, r, c = map(int, input().split())
    g[l-1][r-1] = min(g[l-1][r-1], c)
    flag[l-1] += 1
    flag[r-1] += -1

for i in range(1, n):
    flag[i] += flag[i-1]
    if flag[i-1] != 0:
        g[i][i-1] = 0


def dijkstra(s, n, edges):
    # edges[i][j] : the cost of i→j
    # import 'heap'
    d = [10**13] * n
    d[s] = 0
    q = [(0, s)]
    while q:
        dist_u, u = heappop(q)
        if d[u] < dist_u:
            continue
        for v, c in enumerate(edges[u]):
            if d[v] > dist_u + c:
                d[v] = dist_u + c
                heappush(q, (d[v], v))
    return d


d = dijkstra(0, n, g)
print(d[n-1] if d[n-1] != 10**10 else -1)


### FIXED CODE ###

from heapq import heappop, heappush

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

g = [[] for __ in range(n)]

for _ in range(m):
    l, r, c = map(int, input().split())
    g[l-1].append((r-1, c))

for i in range(1, n):
    g[i].append((i-1, 0))


d = [10**18] * n
d[0] = 0
q = [(0, 0)]
while q:
    dist_u, u = heappop(q)
    if d[u] < dist_u:
        continue
    for v, c in g[u]:
        if d[v] > dist_u + c:
            d[v] = dist_u + c
            heappush(q, (d[v], v))


print(d[n-1] if d[n-1] != 10**18 else -1)
### BUGGY CODE ###

from collections import defaultdict
import sys

def read():
    return sys.stdin.readline().rstrip()

def main():
    n, m, k = map(int, read().split())
    friend, block = defaultdict(set), defaultdict(set)
    for _ in range(m):
        a, b = [int(i) - 1 for i in read().split()]
        friend[a].add(b)
        friend[b].add(a)
    for _ in range(k):
        c, d = [int(i) - 1 for i in read().split()]
        block[c].add(d)
        block[d].add(c)
    i = -1
    belonging = [-1] * n
    group = []
    next_search = []
    is_searched = [False] * n
    while not all(is_searched):
        if not next_search:
            for j, s in enumerate(is_searched):
                if not s:
                    next_search.append(j)
                    group.append(set())
                    i += 1
                    break
        j = next_search.pop()
        if is_searched[j]:
            continue
        is_searched[j] = True
        belonging[j] = i
        group[i].add(j)
        next_search += friend[j]
    suggestion = [len(group[belonging[i]].difference(friend[i]).difference(block[i])) - 1 for i in range(n)]
    print(*suggestion)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import deque

def read():
    return sys.stdin.readline().rstrip()

def main():
    n, m, k = map(int, read().split())
    friend = [[] for _ in range(n)]
    block = [set() for _ in range(n)]
    potential = [set() for _ in range(n)]
    for _ in range(m):
        a, b = [int(i) - 1 for i in read().split()]
        friend[a].append(b)
        friend[b].append(a)
    for _ in range(k):
        c, d = [int(i) - 1 for i in read().split()]
        block[c].add(d)
        block[d].add(c)
    sd = set()
    for u in range(n):
        if u in sd:
            continue
        sn = deque([u])
        pf = set()
        while sn:
            p = sn.pop()
            if p in sd:
                continue
            sd.add(p)
            pf.add(p)
            for f in friend[p]:
                sn.append(f)
        for pfi in pf:
            potential[pfi] = pf
    print(*[len(potential[i]) - len(block[i] & potential[i]) - len(friend[i]) - 1 for i in range(n)])

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

s = int(input())
n = input()
ans = 0
r_set = set()
g_set = set()
b_set = set()

for _ in range(s):
    if n[_] == 'R':
        r_set.add(_)
    elif n[_] == 'G':
        g_set.add(_)
    else:
        b_set.add(_)

for r in r_set:
    for g in g_set:
        for b in b_set:
            mi = min(r, g, b)
            ma = max(r, g, b)
            set_re = {r, g, b} - {mi, ma}
            re = list(set_re)[0]
            if re - mi != ma - re:
                ans += 1

print(ans) 

### FIXED CODE ###

s = int(input())
n = input()
ans = 0
r_set = set()
g_set = set()
b_set = set()

for _ in range(s):
    if n[_] == 'R':
        r_set.add(_)
    elif n[_] == 'G':
        g_set.add(_)
    else:
        b_set.add(_)

len_b = len(b_set)

for r in r_set:
    for g in g_set:
        diff = abs(r - g)
        minus = set()
        if r < g:
            if g + diff in b_set:
                minus.add(g+diff)
            if r - diff in b_set:
                minus.add(r-diff)
        else:
            if r + diff in b_set:
                minus.add(r+diff)
            if g - diff in b_set:
                minus.add(g-diff)
        if (r + g) / 2 in b_set:
            minus.add((r+g)/2)
        ans += len_b - len(minus)

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

# coding : utf-8

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

b = M/N
y = []

for i in range(int(b)):
    if M % (i+1) == 0:
        y.append(i+1)

print(max(y))

### FIXED CODE ###

from math import sqrt
 
n, m = map(int, input().split())
l = []
for i in range(1, int(sqrt(m)) + 1):
	if m % i == 0:
		l.append(i)
		l.append(m // i)
 
ans = 1
for d in l:
	if d * n <= m:
		ans = max(ans, d)
 
print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split())
link = [[0]*(N+1) for _ in range(N+1)]
for n in range(N-1):
    a, b = map(int, input().split())
    link[a][b] = 1
    link[b][a] = 1
V = [0] * (N+1)
ans = [0] * (N+1)
for q in range(Q):
    p, x = map(int, input().split())
    V[p] += x

def dfs(i, parent, acc):
    V[i] += acc
    for j in range(1,N+1):
        if link[i][j] == 1 and parent!=j:
            dfs(j,i,V[i])
cur = 1
parent = 0
acc = 0

dfs(cur, parent , acc)
V = [str(v) for v in V]
print (" ".join(V[1:]))

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

# 遅延評価で加えてあげるだけ

N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

value = [0] * (N+1)
for p,x in PX:
    value[p] += x

def dfs(v,parent,add):
    value[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x,v,value[v])

dfs(1,0,0)

answer = ' '.join(map(str,value[1:]))
print(answer)
### BUGGY CODE ###

if __name__ == '__main__':
	s = input()
	K = int(input())

	subs = set()
	for f in range(len(s)):
		for t in range(f, len(s)+1):
			subs.add(s[f:t])

	l = list(subs)
	l.sort(key=None)
	print(l[K])


### FIXED CODE ###

if __name__ == '__main__':
	s = input()
	K = int(input())

	subs = set()
	if len(s) <= 50:
		for f in range(len(s)):
			for t in range(f, len(s)+1):
				subs.add(s[f:t])
	else:
		for f in range(len(s)):
			for t in range(f, f+6):
				subs.add(s[f:t])

	l = list(subs)
	l.sort()
	print(l[K])
### BUGGY CODE ###

n,p=map(int,input().split())
i,a=2,1
while i**n<=p:
  while p%(i**n)==0:a*=i;p//=(i**n)
  i+=1
print(a)

### FIXED CODE ###

n,p=map(int,input().split())
for i in range(round(p**(1/n)),0,-1):
  if p%(i**n)==0:print(i);exit()
### BUGGY CODE ###

N = int(input())
P = [int(i) for i in input().split()]
P_min = min(P)

count = 1
for i in range(N-1):
    if P[i+1] == P_min:
        count+=1
        break
    if min(P[:i+1]) > P[i+1]:
        count+=1

print(count)

### FIXED CODE ###

# https://atcoder.jp/contests/abc152/submissions/9600286
N = int(input())
P = list(map(int, input().split()))
c = 10**9
count = 0
for i in P:
    #リストの始めから探索
    #minを保持していく
    if i < c:
        c=i
        count+=1
print(count)
### BUGGY CODE ###

import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)
    
k = int(input())
sum = 0
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            sum += gcd(a,b,c)
print(sum)

### FIXED CODE ###

import math
k = int(input())
s = 0
i = 0
d = [0]*k*k
for a in range(1,k+1):
    for b in range(1,k+1):
        d[i] = math.gcd(a,b)
        i+=1
for c in range(1,k+1):
        s += sum(map(lambda x: math.gcd(x,c),d))
print(s)
### BUGGY CODE ###

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

B = []

for i in range(1,N+1):
	idx = A.index(i) + 1
	#print(idx)
	B.append(idx)

print(*B)

### FIXED CODE ###

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

B = [0] * N

for i, a in enumerate(A):
	B[a-1] = i+1
print(*B)
### BUGGY CODE ###

from itertools import product
n, m = map(int, input().split())
can_open = []
cost = []
for _ in range(m):
    a, b = map(int, input().split())
    cost.append(a)
    can_open.append(sum(1 << (c-1) for c in map(int, input().split())))

n_bit = 1 << n
INF = 10**18
dp = [INF]*n_bit
dp[0] = 0

for j, (x, y) in product(range(n_bit), zip(can_open, cost)):
    m = j | x
    dp[m] = min(dp[m], dp[j]+y)

print(dp[-1] if dp[-1] != INF else -1)

### FIXED CODE ###

n, m = map(int, input().split())
can_open = []
cost = []
for _ in range(m):
    a, b = map(int, input().split())
    cost.append(a)
    it = map(int, input().split())
    x = 0
    for c in it:
        x += 1 << (c-1)
    can_open.append(x)

n_bit = 1 << n
INF = 10**18
dp = [[INF]*n_bit for _ in range(m+1)]
dp[0][0] = 0

# 配る
for i in range(m):
    for j in range(n_bit):
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

        if (j | can_open[i]) <= n_bit:
            dp[i+1][j | can_open[i]
                    ] = min(dp[i+1][j | can_open[i]], dp[i+1][j]+cost[i])

print(dp[-1][-1] if dp[-1][-1] != INF else -1)
### BUGGY CODE ###

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

# nの約数を求める。計算量O(sqrt(N))
def get_divisors(n):
    from math import sqrt, ceil
    divisors = []
    for num in range(ceil(sqrt(n)), n+1):
        if n % num == 0:
            divisors.append(n//num)
            if n//num != n:
                divisors.append(num)
    divisors.sort(reverse=True)
    return divisors

total = sum(A)
divisors = get_divisors(total)
ans = -1
for d in divisors:
    R = [a%d for a in A]
    R.sort(reverse=True)
    pr = 0
    nr = -sum(R)
    for i, r in enumerate(R):
        pr += d-r
        nr += r
        if nr+pr >= 0:
            if pr <= K and nr+pr == 0:
                ans = d
            break
    if ans != -1:
        print(ans)
        break
else:
    print(1)


### FIXED CODE ###

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

# nの約数を求める。計算量O(sqrt(N))
def get_divisors(n):
    from math import sqrt, ceil
    from collections import deque
    divisors = deque([])
    for num in range(ceil(sqrt(n)), n+1):
        if n % num == 0:
            divisors.append(n//num)
            if n//num != n:
                divisors.appendleft(num)
    return list(divisors)


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n//i:
                divisors.append(n//i)
    divisors.sort(reverse=True)
    return divisors

total = sum(A)
divisors = make_divisors(total)
ans = -1
for d in divisors:
    R = [a%d for a in A]
    R.sort(reverse=True)
    pr = 0
    nr = -sum(R)
    for i, r in enumerate(R):
        pr += d-r
        nr += r
        if nr+pr >= 0:
            if pr <= K and nr+pr == 0:
                ans = d
            break
    if ans != -1:
        print(ans)
        break
else:
    print(1)
### BUGGY CODE ###

n = int(input())
A = [int(input()) for i in range(n)]

#shellSort
cnt = 0

G = []
tg = 1
while tg <= n:
    G.insert(0, tg)
    tg = 3 * tg + 1

m = len(G)

for i in range(m):
    g = G[i]
    # insertionSort
    for j in range(g, n):
        k = j - g
        while (k >= 0) and (A[k] > A[k + g]):
            A[k + g], A[k] = A[k], A[k + g]
            k -= g
            cnt += 1

print(m)
print(*G)
print(cnt)
for i in A:
    print(i)

### FIXED CODE ###

import sys

def insertionSort(A, n, g):
    global cnt
    for i in range(g, n):
        v = A[i]
        j = i - g
        while (j >= 0) and (A[j] > v):
            A[j + g] = A[j]
            j = j - g
            cnt += 1
        A[j + g] = v

def shellSort(A, n):
    G = [i for i in [262913, 65921, 16577, 4193, 1073, 281, 77, 23, 8, 1] if i <= n]
    m = len(G)
    for k in range(m):
        insertionSort(A, n, G[k])
    return m, G

A = list(map(int, sys.stdin))
n = A[0]
del A[0]

cnt = 0

m, G = shellSort(A, n)

print(m)
print(*G)
print(cnt)
print("\n".join(map(str, A)))
### BUGGY CODE ###

import numpy as np
 
n = int(input())
a = list(map(int, input().split()))

counter = [0 for _ in range(n)]
for num in a:
    div = np.array(a) % num
    for j, index in enumerate(div):
        if index == 0:
            counter[j] += 1
print(counter.count(1))

### FIXED CODE ###

import numpy as np
 
n = int(input())
a = list(map(int, input().split()))
a.sort()
dp = [0 for _ in range(a[-1] + 1)]

for x in a:
    for j in range(x, a[-1] + 1, x):
        dp[j] += 1
ans = 0
for x in set(a):
    #print(x)
    if dp[x] == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

import math

def comb_count(n, r):
    return math.factorial(n) // math.factorial(r) * math.factorial(n - r)

S = input()[::-1]
ans = 0

mods = [0] * 2019 #余りが0~2018
mods[0] = 1
current = 0

for i in range(len(S)):
    current = (int(S[i]) * 10 ** i + current) % 2019
    mod = current % 2019
    mods[mod] += 1

i = 0
for mod in mods:
    if mod > 1:
        ans += comb_count(mod, 2)
print(ans)



### FIXED CODE ###

import math

# def comb_count(n, r):
#     return math.factorial(n) // math.factorial(r) // math.factorial(n - r)

S = input()[::-1]
ans = 0

mods = [0] * 2019 #余りが0~2018
mods[0] = 1
current = 0
tmp = 1

for i in range(len(S)):
    current = (int(S[i]) * tmp + current) % 2019
    mod = current % 2019
    ans += mods[mod]
    mods[mod] += 1
    tmp = tmp * 10 % 2019

# for mod in mods:
#     if mod > 1:
#         ans += comb_count(mod, 2)
print(ans)
### BUGGY CODE ###

from bisect import bisect_left
from decimal import Decimal

N, *A = map(Decimal, open(0).read().split())
N = int(N)
A.sort()

c = {}
intc = 0
ints = []
decs = []
for d in A:
    if d in c:
        c[d] += 1
        if d == int(d):
            intc += 1
    else:
        c[d] = 1
        if d == int(d):
            intc += 1
            ints.append(d)
        else:
            decs.append(d)

result = intc * (intc - 1) // 2
for i in range(len(decs)):
    a = decs[i]
    f = a - int(a)
    t = max(bisect_left(decs, 1 / a), i + 1)
    for j in range(t, len(decs)):
        b = decs[j]
        t = a * b
        if t == int(t):
            result += c[a] * c[b]

fras = sorted(set(d - int(d) for d in decs))
frac = {}
for d in decs:
    t = d - int(d)
    frac.setdefault(t, 0)
    frac[t] += c[d]

for i in range(len(fras)):
    a = fras[i]
    t = bisect_left(ints, 1 / a)
    for j in range(t, len(ints)):
        b = ints[j]
        t = a * b
        if t == int(t):
            result += frac[a] * c[b]

print(result)


### FIXED CODE ###

def conv(s):
    if s.find('.') == -1:
        s += '.'
    s = s.rstrip('0')
    t = len(s) - s.find('.') - 1
    a = int(s.replace('.', ''))
    if a == 0:
        return (0, 0)
    x, y = -t, -t
    while a % 5 == 0:
        x += 1
        a //= 5
    while a % 2 == 0:
        y += 1
        a //= 2
    return (x, y)


N, *A = open(0).read().split()
N = int(N)

d = {}
for a in A:
    t = conv(a)
    d.setdefault(t, 0)
    d[t] += 1

result = 0
xs = list(d.keys())
for i in range(len(xs)):
    x, y = xs[i]
    t = d[xs[i]]
    if x >= 0 and y >= 0:
        result += t * (t - 1) // 2
    for j in range(i + 1, len(xs)):
        m, n = xs[j]
        if x + m >= 0 and y + n >= 0:
            result += t * d[xs[j]]
print(result)
### BUGGY CODE ###

mod = 998244353
N,M,K = map(int,input().split())
ans = 0
def pow(x,n):
    if n == 0:  
        return 1
    if n % 2 == 0:  
        return pow((x ** 2)%mod, n // 2)%mod
    else:
        return x * pow((x ** 2)%mod, (n - 1) // 2)%mod
A = 1
for i in range(K+1):
    p = N - i
    x = M*pow(M-1,p-1)*A % mod
    ans += x
    A *= (N-i-1)
    y = pow(i+1,mod-2)
    A *= y
    A %= mod
print(ans%mod)

### FIXED CODE ###

mod = 998244353
N,M,K = map(int,input().split())
ans = 0
def pow(x,n):
    if n == 0:  
        return 1
    if n % 2 == 0:  
        return pow((x ** 2)%mod, n // 2)%mod
    else:
        return x * pow((x ** 2)%mod, (n - 1) // 2)%mod
A = 1
for i in range(K+1):
    p = N - i
    x = M*pow(M-1,p-1)*A % mod
    ans += x
    A = A*(N-i-1)%mod
    y = pow(i+1,mod-2)
    A = A*y % mod
print(ans%mod)
### BUGGY CODE ###

N, K = map(int, input().split())
S=0
for b in range(K+1,N+1):
    S += (b-K)*(N//b)
    if N%b>=K:
        for a in range(N,b*(N//b),-1):
            if a%b>=K:
                S+=1
            else:
                break
print(S)


### FIXED CODE ###

N, K = map(int, input().split())
S=0
for b in range(K+1,N+1):
    S += (b-K)*(N//b)
    #print(S,b,-1,N,K)
    M=(b*(N//b))+K
    if N%b>=K:
        S+=(N-M)
        if K!=0:
            S+=1
        #print(b)
        #print(S,b,M,N,K)
print(S)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
BC = [list(map(int, input().split())) for _ in range(Q)] 
ans = [0]*(10**5+1)
for i in range (len(A)):
    ans[A[i]] += 1
maxlen = max(max(A),max(max(BC)))
for i in range(Q):
    ans[BC[i][1]] += ans[BC[i][0]]
    ans[BC[i][0]] = 0 

    S = 0
    for i in range(maxlen+1):
        S += ans [i]*i
    print(S)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
BC = [list(map(int, input().split())) for _ in range(Q)] 
ans = [0]*(10**5+1)

for i in range (len(A)):
    ans[A[i]] += 1
maxlen = max(max(A),max(max(BC)))
S = 0
for i in range(maxlen+1):
        S += ans [i]*i
for i in range(Q):
    ans[BC[i][1]] += ans[BC[i][0]]
    S = S + ans[BC[i][0]] *BC[i][1] - ans[BC[i][0]]*BC[i][0]
    ans[BC[i][0]] = 0
    print(S)
### BUGGY CODE ###

def merge(A, left, mid, right):

    n1 = mid-left
    n2 = right-mid
    L = [0 for i in range(n1+1)]
    R = [0 for i in range(n2+1)]
    for i in range(n1):
        L[i] = A[left+i]
    for i in range(n2):
        R[i] = A[mid+i]
    L[n1] = 2000000000
    R[n2] = 2000000000
    i = 0
    j = 0
    #global cnt
    cnt = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i+1
            cnt +=1
        else:
            A[k] = R[j]
            j = j+1
            cnt +=1
    return cnt

def mergeSort(A, left, right):
    if left+1 < right:
         mid = (left+right) // 2
         cnt1 = mergeSort(A, left, mid)
         cnt2 = mergeSort(A, mid, right)
         cnt3 = merge(A, left, mid, right)
         return cnt1+cnt2+cnt3
    else:
        return 0

n = input()
A = list(map(int, input().split()))
cnt = mergeSort(A, 0, len(A))
print(*A)
print(str(cnt))

### FIXED CODE ###

def merge(A, left, mid, right):

    n1 = mid-left
    n2 = right-mid
    #L = [0 for i in range(n1+1)]
    #R = [0 for i in range(n2+1)]
    #for i in range(n1):
    #    L[i] = A[left+i]
    #for i in range(n2):
    #    R[i] = A[mid+i]
    L = A[left:mid]
    R = A[mid:right]
    L.append(float('inf'))
    R.append(float('inf'))
    i = 0
    j = 0
    global cnt

    for k in range(left, right):
        cnt += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i+1
        
        else:
            A[k] = R[j]
            j = j+1
    return cnt

def mergeSort(A, left, right):
    if left+1 < right:
         mid = (left+right) // 2
         mergeSort(A, left, mid)
         mergeSort(A, mid, right)
         merge(A, left, mid, right)
    else:
        return 0

n = input()
A = list(map(int, input().split()))
cnt = 0
mergeSort(A, 0, len(A))
print(*A)
print(str(cnt))
### BUGGY CODE ###

print(sum(range(int(input()))))

### FIXED CODE ###

print(sum(range(int(input()))))