Harryxun/stf_run huggingface dataset:
n = int(input())
a = list(map(int,input().split()))
a.sort()
b = [2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 
     131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 
     67108864, 134217728, 268435456, 536870912]

t = []
bIdx = 0
for aa in a :
    while b[bIdx] <= aa:
        bIdx += 1   
    t.append(b[bIdx]-aa)

t.reverse()
a.sort(reverse=True)

#print(t,a)
sum = 0
i = 0

u = [0 for i in range(len(a))]

for i in range(len(a)-1):

    if u[i] > 0:
        continue

    first = i+1
    last = len(a)-1
    found = False
 
    while first<=last and not found:
        midpoint = (first + last)//2
        if a[midpoint] == t[i] and u[i] <= 0:
            found = True
            sum += 1
            a.pop(midpoint)
            u[i] +=1
        else:
            if t[i] > a[midpoint]:
                last = midpoint-1
            else:
                first = midpoint+1
    
print(sum)

### FIXED CODE ###

from bisect  import bisect_left

n = int(input())
a = list(map(int,input().split()))
a.sort()
#print(a)

sum = 0
for i in range (len(a)-1,-1,-1):

    b = 1
    while b <= a[i]:
        b = b<<1
    t = b - a[i]
    #print("2^",t)

    k = bisect_left(a,t)
    if a[k] == t and k < i:
        sum += 1
        a[k] -= 0.1
        a[i] += 0.1
print(sum)
n = int(input())
a = list(map(int,input().split()))
sss = 0
for i in range(n):
    sss=sss + a[i]
ppp = 0
qqq = abs(sss - 2 * a[0])
for i in range(n):
    ppp=ppp + a[i]
    qo = abs(sss-2ppp)
    if qqq > qo:
        qqq=qo
        
print(qqq)

### FIXED CODE ###


n = int(input())
a = list(map(int,input().split()))
sss = 0
for i in range(n):
    sss=sss + a[i]
ppp = 0
qqq = abs(sss - 2 * a[0])
for i in range(n-1):
    ppp=ppp + a[i]
    qo = abs(sss-2*ppp)
    if qqq > qo:
        qqq=qo
        
print(qqq)
def memoize(f): #メモ化関数
  table = {}
  def func(*args):
    if not args in table:
      table[args] = func(*args)
    return table[args]
  return func
  
@memoize
def fac(x):
  if x==0:
    return 1
  else:
    return x*fac(x-1)

N=int(input())

def divisor(n): #nの約数を全て求める
    i = 1
    while i * i < n:
        if n%i == 0:
            table.append(i)
            
        i += 1
    table = list(set(table))
    return table

def make_divisors(n):
    cnt=0
    i=1
    while i * i < n:
      if n%i == 0:
        cnt+=2            
        i += 1
    if i*i==n:
      cnt+=1
    return cnt
ans1=fac(N)
ans2=make_divisors(ans1)%(10**9+7)
print(ans2)

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    l = [0 for _ in range(N)]
    is_prime = [True for _ in range(N+1)]
    is_prime[0],is_prime[1] = False,False
    INF = 10**9+7
    
    for i in range(N+1):
        if is_prime[i]:
            for j in range(2*i,N+1,i):
                is_prime[j] = False

    fa = [0 for _ in range(N+1)]                
    for x in range(1,N+1):
        for i in range(1,x+1):
            if (is_prime[i] and x%i == 0):
                while x%i == 0:
                    fa[i] += 1
                    x //= i
 
    ans = 1
    for i in range(N+1):
        ans *= fa[i]+1
        ans %= INF
        
    print(ans)
    
if __name__ == "__main__":
    main()
import math
a, b = map(int, input().split)
c = int(str(a)+str(b))
if math.sqrt(c) % 2 == 0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

import math
a, b = map(int, input().split())
c = int(str(a)+str(b))
if math.sqrt(c) - int(math.sqrt(c))== 0:
  print("Yes")
else:
  print("No")
k = int(input())
s = input()

if k < len(s):
  s = s[0,k]+"..."
print(s)



### FIXED CODE ###

K = int(input())
S = input()

if len(S) > K:
  S = S[:K] + "..."

print(S)
from collections import deque
import numpy as np
n, k = map(int, input().split())
An = list(map(int, input().split()))
root = deque([1])
check = np.zeros(n, np.int)
check[0] = 1
i = 0
dup = 1
cnt = 1
for _ in range(n):
    temp = An[i]
    if check[temp-1] == 1:
        dup = temp
        break
    root.append(temp)
    check[temp-1] = 1
    i = temp - 1
    cnt += 1
index = root.index(dup)
if index <= k:
    print(root[k-1])
elif index == cnt - 1:
    print(dup)
else:
    print(root[(k-index) % (cnt-index) + index])


### FIXED CODE ###

from collections import deque
import numpy as np
n, k = map(int, input().split())
An = list(map(int, input().split()))
root = deque([1])
check = np.zeros(n, np.int)
check[0] = 1
i = 0
dup = 1
cnt = 1
for _ in range(n):
    temp = An[i]
    if check[temp-1] == 1:
        dup = temp
        break
    root.append(temp)
    check[temp-1] = 1
    i = temp - 1
    cnt += 1
index = root.index(dup)
if index >= k:
    print(root[k])
elif index == cnt - 1:
    print(dup)
else:
    print(root[(k-index) % (cnt-index) + index])
n,m=map(int,input().split())
g=[ [0 for _ in range(8)] for _ in range(8)]
a=[0]*m
b=[0]*m
for i in range(m):
    a[i],b[i]=map(lambda x:int(x)-1,input().split())
    g[a[i]][b[i]]=1
    g[b[i]][a[i]]=1
ans=0
#print(g)
for i in range(m):
#    print(i,end=' start i \n')
    g[a[i]][b[i]]=0
    g[b[i]][a[i]]=0
    vis=[0]*n
    def dfs(u):
        vis[u]=1
#        print(u,end=' dfs\n')
        for j in range(n):
            if j!=u and g[u][j]==1 and vis[j]==0:
                dfs(j)
    bridge=False
    dfs(0)
    for j in range(n):
        #print(i,vis)
        if vis[j]==0:
            bridge=True
    if bridge:
        ans+=1
    #print(i,end=' curr i \n')
    g[a[i]][b[i]]=1
    g[b[i]][a[i]]=1
print(ans)



### FIXED CODE ###

n,m=map(int,input().split())
g=[ [0 for _ in range(50)] for _ in range(50)]
a=[0]*m
b=[0]*m
for i in range(m):
    a[i],b[i]=map(lambda x:int(x)-1,input().split())
    g[a[i]][b[i]]=1
    g[b[i]][a[i]]=1
ans=0
#print(g)
for i in range(m):
#    print(i,end=' start i \n')
    g[a[i]][b[i]]=0
    g[b[i]][a[i]]=0
    vis=[0]*n
    def dfs(u):
        vis[u]=1
#        print(u,end=' dfs\n')
        for j in range(n):
            if j!=u and g[u][j]==1 and vis[j]==0:
                dfs(j)
    bridge=False
    dfs(0)
    for j in range(n):
        #print(i,vis)
        if vis[j]==0:
            bridge=True
    if bridge:
        ans+=1
    #print(i,end=' curr i \n')
    g[a[i]][b[i]]=1
    g[b[i]][a[i]]=1
print(ans)
N = int(input())
A = [int(input()) for _ in range(N)]
first = []
for a in A:
    i = bisect.bisect_left(first,a)
    if i == 0:
        first.insert(0,i)
    else:
        first[i-1] = a
print(len(first))

### FIXED CODE ###

import bisect
N = int(input())
A = [int(input()) for _ in range(N)]
first = [-1 for _ in range(N)]
for a in A:
    i = bisect.bisect_left(first,a)
    first[i-1] = a
ctr = N
for f in first:
    if f == -1:
        ctr -= 1
print(ctr)
# 入力の受け取り
n = int(input())
list = list(input().split())

# 全種類用意しとく
alphabets_list = lsit("abcdefghijklmnopqrstuvwxyz".split())

# 判定
for i in range(1, n - 1):
    x = list[ :i]
    y = list[i: ]
    count = 0
    for alphabet in alphabets_list:
        if alphabet in x and alphabet in y:
            count += 1
        else:
            continue

print(continue)


### FIXED CODE ###

# 入力の受け取り
n = int(input())
s = input()

# 全種類用意しとく
alphabets_list = [c for c in "abcdefghijklmnopqrstuvwxyz"]

# 判定
result = []
for i in range(1, n):
    x = s[ :i]
    y = s[i: ]
    count = 0
    for alphabet in alphabets_list:
        if (alphabet in x) and (alphabet in y):
            count += 1
        else:
            count += 0
    result.append(count)

print(max(result))
import sys
input = sys.stdin.readline
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    flag = True
    D = 0
    now = 1
    LOG = {}
    PATH = []
    for i in range(N):
        PATH.append(D)
        LOG.setdefault(D,i)

        if LOG[D] == i:
            D = A[D]-1
            continue
        else:
            print("break",D)
            start = D
            break
        # print(PATH, D)
    K = K%i
    LAST = PATH[LOG[D] + K] +1
    print(LAST)



if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    D = 1
    LOG = {}
    PATH = []
    for i in range(N):
        PATH.append(D)
        LOG.setdefault(D,i)

        if LOG[D] == i:
            D = A[D-1]
            # print(PATH,LOG, i)
            continue
        else:
            # print("break",D, i)
            break

    # if i-LOG[D] < K:
    if LOG[D] < K:
        K = (K-i)%(i-LOG[D])
        LAST = PATH[LOG[D]+K]
    else:
        LAST = PATH[K]
    print(LAST)

if __name__ == '__main__':
    main()
n = int(input())

li = []
for i in range(n):
    li.append(list(map(str, input().split())))
    li[i].append(i+1)

li.sort( key = lambda li : (li[0], -int(li[1])))
for i in li:
    print(li[2])


### FIXED CODE ###

n = int(input())

li = []
for i in range(n):
    li.append(list(map(str, input().split())))
    li[i].append(i+1)

li.sort( key = lambda li : (li[0], -int(li[1])))
for i in li:
    print(i[2])
alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
H, W = map(int, raw_input().split())
S = [raw_input().split() for i in xrange(H)]

for h in xrange(H):
	for w in xrange(W):
		if S[h][w] == "snuke":
			print alpha[w] + str(h + 1)
			exit()
torii@xps45:~/roiti46/procon/Contest/2

### FIXED CODE ###

alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
H, W = map(int, raw_input().split())
S = [raw_input().split() for i in xrange(H)]

for h in xrange(H):
	for w in xrange(W):
		if S[h][w] == "snuke":
			print alpha[w] + str(h + 1)
			exit()
A, B, K =map(int,input().split())

if B-A <= K:
  for i in range(A, B):
    print(i)
else:
  C = []
  for i in range(A, A+K):
    C.append(i)
  
  D = []  
  for i in range(B, B-K+1, -1) :
    D.append(i)

E = set(C) | set(D)
F = sorted(E)
print(F)


### FIXED CODE ###

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

if B-A <= K:
  for i in range(A, B+1):
    print(i)
else:
  C = []
  for i in range(A, A+K):
    C.append(i)
  
  D = []  
  for i in range(B, B-K, -1) :
    D.append(i)
    
  E = set(C) | set(D)
  F = sorted(E)
  
  for i in range(len(F)):
      print(F[i])
from collections import deque, defaultdict

def topological_sort(V, E):
    '''
    Kahn's Algorithm (O(|V| + |E|) time)
    Input:
    V = [0, 1, ..., N-1]: a list of vertices of the digraph
    E: the adjacency list of the digraph (dict)
    Output:
    If the input digraph is acyclic, then return a topological sorting of the digraph.
    Else, return None.
    '''
    indeg = {v: 0 for v in V}
    for ends in E.values():
        for v in ends:
            indeg[v] += 1
    
    q = deque([v for v in V if indeg[v] == 0])
    top_sorted = []
    while q:
        v = q.popleft()
        top_sorted.append(v)
        
        for u in E[v]:
            indeg[u] -= 1
            if indeg[u] == 0:
                q.append(u)
    if len(top_sorted) == len(V): # The input digraph is acyclic.
        return top_sorted
    else: # There is a directed cycle in the digraph.
        return None

N, M = map(int, input().split())
E = defaultdict(list)
for _ in range(M):
    s, t = map(int, input().split())
    E[s].append(t)
print(*topological_sort(V, E), sep='\n')


### FIXED CODE ###

from collections import deque, defaultdict

def topological_sort(V, E):
    '''
    Kahn's Algorithm (O(|V| + |E|) time)
    Input:
    V = [0, 1, ..., N-1]: a list of vertices of the digraph
    E: the adjacency list of the digraph (dict)
    Output:
    If the input digraph is acyclic, then return a topological sorting of the digraph.
    Else, return None.
    '''
    indeg = {v: 0 for v in V}
    for ends in E.values():
        for v in ends:
            indeg[v] += 1
    
    q = deque([v for v in V if indeg[v] == 0])
    top_sorted = []
    while q:
        v = q.popleft()
        top_sorted.append(v)
        
        for u in E[v]:
            indeg[u] -= 1
            if indeg[u] == 0:
                q.append(u)
    if len(top_sorted) == len(V): # The input digraph is acyclic.
        return top_sorted
    else: # There is a directed cycle in the digraph.
        return None

N, M = map(int, input().split())
V = range(N)
E = defaultdict(list)
for _ in range(M):
    s, t = map(int, input().split())
    E[s].append(t)
print(*topological_sort(V, E), sep='\n')
def f(b,n):
    if n<b:
        return n
    return f(b,n//b) + n % b

if n < s or (n // 2)+1 < s < n :
    print("-1")
elif s == n:
    print(n+1)
elif s == n//2 +1:
    if n % 2 == 1:
        print(n//2 + 1)
    else:
        print("-1")
elif (n//3) + 2 < s <= n//2:
    print(n-s+1)
elif s == 1:
    def check(n,b):
        if n == 1:
            return b
        else:
            if n % b !=0 :
                return 0
            else:
                return check(n // b,b)
    for b in range(2,rtn):
        r = check(n,b)
        if r:
            print(r)
            exit()
    print(n)
else:
    x = n // s
    if s - (n //(x+1))  <= x:
        x = x + 1
    if 5 < n/(x -1) - n/x :
        for b in range(n//x, n//(x-1)):
            if f(b,n) == s:
                print(b)
                exit()
        for i in range(x-1,2,-1):
            for b in range(n//i + (n//x)//(n//i), n//i + (n//x)//(n//i)  + (2*n//x - n//(x+1))//(x-i)):
                if f(b,n) == s:
                    print(b)
                    exit()
    else:
        for b in range(2,(n//3)+3):
            if f(b,n) == s:
                print(b)
                exit()
    print(n-s+1)


### FIXED CODE ###

n = int(input())
s = int(input())
rtn = -1* int( -1 * (n**0.5))
def f(b,n):
    if n<b:
        return n
    return f(b,n//b) + n % b
if n < s or (n // 2)+1 < s < n :
    print("-1")
elif s == n:
    print(n+1)
elif s == n//2 +1:
    if n % 2 == 1:
        print(n//2 + 1)
    else:
        print("-1")
elif (n//3) + 2 < s <= n//2:
    print(n-s+1)
else:
    for b in range(2,rtn+1):
        if f(b,n) == s:
            print(b)
            exit()
    for p in range(rtn,0,-1):
        if (n-s) % p == 0:
            b = (n-s)//p + 1
            if f(b,n) == s:
                print(b)
                exit()
    print(n-s+1)
# import sys
# sys.setrecursionlimit(2147483647)

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


vertice = [-1 for _ in range(n)]
stack = [(0, 0)]

while stack:
    parent, vertex = stack.pop()
    vertice[vertex] = vertice[parent] * (-1)
    for next in edges[vertex]:
        if next != parent:
            stack.append((vertex, next))

# vertice = [0 for _ in range(n)]
#
#
# def dfs(v, color_i):
#     vertice[v] = color_i
#     for i in edges[v]:
#         if vertice[i] == 0:
#             dfs(i, color_i*(-1))
#
# dfs(0, 1)

ans = []
if vertice.count(1) <= n // 3:
    not3 = [i for i in range(1, n+1) if i % 3 != 0]
    num3 = [i for i in range(1, n+1) if i % 3 == 0]
    for v in vertice:
        if v == 1:
            if num3:
                ans.append(str(num3.pop()))
            else:
                ans.append(str(not3.pop()))
        else:
            ans.append(str(not3.pop()))
elif vertice.count(-1) <= n // 3:
    not3 = [i for i in range(1, n+1) if i % 3 != 0]
    num3 = [i for i in range(1, n+1) if i % 3 == 0]
    if v == -1:
        if num3:
            ans.append(str(num3.pop()))
        else:
            ans.append(str(not3.pop()))
    else:
        ans.append(str(not3.pop()))
else:
    num1 = [i for i in range(1, n+1) if i % 3 == 1]
    num2 = [i for i in range(1, n+1) if i % 3 == 2]
    num3 = [i for i in range(1, n+1) if i % 3 == 0]
    for v in vertice:
        if v == 1:
            if num1:
                ans.append(str(num1.pop()))
            else:
                ans.append(str(num3.pop()))
        else:
            if num2:
                ans.append(str(num2.pop()))
            else:
                ans.append(str(num3.pop()))

print(" ".join(ans))


### FIXED CODE ###

n = int(input())
edge = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)
 
group = [False] * n
parent = list(range(n))
stack = [0]
while stack:
  v = stack.pop()
  while edge[v]:
    u = edge[v].pop()
    if parent[v] != u:
      group[u] = not group[v]
      parent[u] = v
      stack.append(u)
 
three = 3
p = [0] * n
if group.count(False) <= n // 3:
  other = 1
  for i in range(n):
    if group[i] and other <= n:
      p[i] = other
      other += other % 3
    else:
      p[i] = three
      three += 3
elif group.count(True) <= n // 3:
  other = 1
  for i in range(n):
    if not group[i] and other <= n:
      p[i] = other
      other += other % 3
    else:
      p[i] = three
      three += 3
else:
  one, two = 1, 2
  for i in range(n):
    if group[i] and one <= n:
      p[i] = one
      one += 3
    elif not group[i] and two <= n:
      p[i] = two
      two += 3
    else:
      p[i] = three
      three += 3
print(' '.join(map(str, p)))
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
ope = []
for _ in range(M):
  ope.append(list(map(int, input().split())))
for m in ope:
  for i in range(m[0]):
    if m[1] > A[i]:
      A[i] = m[1]
	A.sort()
print(sum(A))      

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
pool = []
[pool.append((a, 1)) for a in A]
for _ in range(M):
  b, c = (map(int, input().split()))
  pool.append((c, b))
pool.sort(reverse=True, key=lambda x:x[0])

while N>0:
  for p in pool:
    if p[1] >= N:
      ans += p[0]*N
      N = 0
    if p[1] < N:
      ans += p[0]*p[1]
      N -= p[1]

print(ans)
import sys
import math
import heapq
import bisect

sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N,M=LI()
As=LI()
As.sort()
len_As = len(As)
Acum=[As[0]]
for i in range(1, len_As):
    Acum.append(Acum[i-1]+As[i])
# print(As)
# print(Acum)

ok = 0
ng = 2*max(As)+1

pat = 0
sm = 0
while ng - ok > 1:
    mid_sum = (ok + ng)//2
    pat = 0
    sm = 0
    for A in As:
        A2 = mid_sum - A
        # print(A2)
        lft = bisect.bisect_left(As, A2)
        pat += len_As - lft
        sm += Acum[len_As-1] - (lft and Acum[lft-1]) + (len_As - lft)*A
    # print(pat, M, ok, ng)

    if pat < M: ng = mid_sum
    else: ok = mid_sum

pat = 0
sm = 0
for A in As:
    A2 = ok - A
    # print(A2)
    lft = bisect.bisect_left(As, A2)
    pat += len_As - lft
    sm += Acum[len_As-1] - (lft and Acum[lft-1]) + (len_As - lft)*A

# print("lo:{} hi:{} pat:{} sum:{}".format(ok, ng, pat, sm))

print(sm - (pat-M)*ok)


### FIXED CODE ###

import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

S,T=LS()
print(T+S)
import sys
sys.setrecursionlimit(10**5)
N,A,B,C = map(int,input().split())
Q = []
ans = []
f = 0
def dfs(f,a,b,c):
    if f == N:return True
    if Q[f] == 'AB':
        if a>0 and dfs(f+1,a-1,b+1,c):
            ans.append('A')
            return True
        if b>0 and dfs(f+1,a+1,b-1,c):
            ans.append('B')
            return True
        
        return False
    if Q[f] == 'BC':
        if b>0 and dfs(f+1,a,b-1,c+1):
            ans.append('B')
            return True
        if c>0 and dfs(f+1,a,b+1,c-1):
            ans.append('C')
            return True
        
        return False
    if Q[f] == 'AC':
        if a>0 and dfs(f+1,a-1,b,c+1):
            ans.append('A')
            return True
        if c>0 and dfs(f+1,a+1,b,c-1):
            ans.append('C')
            return True
        
        return False
    

for i in range(N):
    s = input()
    Q.append(s)
dfs(0,A,B,C)
# print(ans)
if len(ans) == N:
    print('Yes')
    ans = ans[::-1]
    for i in ans:
        print(i)
else:
    print('No')


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
N,A,B,C = map(int,input().split())
Q = []
ans = []
f = 0
def dfs(f,a,b,c):
    if f == N:return True
    if Q[f] == 'AB':
        if a+b == 0:return False
        if b>0 and dfs(f+1,a+1,b-1,c):
            ans.append('A')
            return True
        if a>0 and dfs(f+1,a-1,b+1,c):
            ans.append('B')
            return True
        
        return False
    if Q[f] == 'BC':
        if c+b == 0:return False
        if c>0 and dfs(f+1,a,b+1,c-1):
            ans.append('B')
            return True
        if b>0 and dfs(f+1,a,b-1,c+1):
            ans.append('C')
            return True
        
        return False
    if Q[f] == 'AC':
        if a+c == 0:return False
        if c>0 and dfs(f+1,a+1,b,c-1):
            ans.append('A')
            return True
        if a>0 and dfs(f+1,a-1,b,c+1):
            ans.append('C')
            return True
        
        return False
    

for i in range(N):
    s = input()
    Q.append(s)
dfs(0,A,B,C)
# print(ans)
if len(ans) == N:
    print('Yes')
    ans = ans[::-1]
    for i in ans:
        print(i)
else:
    print('No')
import sys
readline = sys.stdin.readline


def main():
    N = int(input())
    As = list(map(int, input().split()))

    edges = (map(int, readline().strip().split()) for _ in range(N-1))

    tree = [[] for _ in range(N)]
    for u, v in edges:
        tree[u-1].append(v-1)
        tree[v-1].append(u-1)

    inf = 10 ** 18
    dp = [inf] * (N+1)
    ans = [0] * N

    def dfs(node, parent):
        v = As[node]
        lb = binary_search(dp, v)
        old = dp[lb]
        dp[lb] = v
        ans[node] = binary_search(dp, inf)
        for child in tree[node]:
            if child == parent:
                continue
            dfs(child, node)
        dp[lb] = old

    dfs(0, 0)

    for k in range(N):
        print(ans[k])


def binary_search(seq, v):
    left = 0
    right = len(seq) - 1
    center = right // 2

    while left != right:
        if v <= seq[center]:
            right = center
        else:
            left = center+1
        center = (right + left) // 2

    return center


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
readline = sys.stdin.readline

sys.setrecursionlimit(10**6)


def main():
    N = int(input())
    As = list(map(int, input().split()))

    query = (map(int, readline().strip().split()) for _ in range(N-1))

    tree = [[] for _ in range(N)]
    for u, v in query:
        tree[u-1].append(v-1)
        tree[v-1].append(u-1)

    inf = 10 ** 18
    dp = [inf] * (N+1)
    ans = [0] * N

    def dfs(node, parent):
        v = As[node]
        lb = binary_search(dp, v)
        old = dp[lb]
        dp[lb] = v
        ans[node] = binary_search(dp, inf)
        for child in tree[node]:
            if child == parent:
                continue
            dfs(child, node)
        dp[lb] = old

    dfs(0, 0)

    for k in range(N):
        print(ans[k])


def binary_search(seq, v):
    left = 0
    right = len(seq) - 1
    center = right // 2

    while left != right:
        if v <= seq[center]:
            right = center
        else:
            left = center+1
        center = (right + left) // 2

    return center


if __name__ == "__main__":
    main()