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

def main():
    s = input()
    q = int(input())
    r = 1
    for _ in range(q):
        n, *fc = input().split()
        if n == "1":
            r *= -1
        else:
            f, c = fc
            f = 1 if f == "1" else -1
            if f*r == 1:
                s = c+s
            else:
                s = s+c
    print(s[::r])
                
            

if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque
def main():
    s = deque(list(input()))
    q = int(input())
    r = 1
    for _ in range(q):
        n, *fc = input().split()
        if n == "1":
            r *= -1
        else:
            f, c = fc
            f = 1 if f == "1" else -1
            if f*r == 1:
                s.appendleft(c)
            else:
                s.append(c)
    print("".join(list(s)[::r]))

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

#from matplotlib import pyplot as plt

def rule2(x,y,z):
    return x ** 2 + y ** 2 + z**2 + x * y + y * z + z*x
def main():
    n = int(input())
    x = []
    y = []
    for i in range(1,n+1):
        x.append(i)
        y.append(f(i))
        print(f(i))
    #plt.scatter(x,y)
    #plt.show()


def f(n):
    counter = 0
    for x in range(1,n):
        if x ** 2 > n:
            break
        for y in range(1,n-x**2):
            if y < x:
                continue
            if x ** 2 + y ** 2 > n:
                break
            for z in range(1,n-x**2-y**2):
                if z < y:
                    continue
                if x ** 2 + y ** 2 + z **2 > n:
                    break
                if rule2(x,y,z) == n:
                    if x == y and y == z and z == x:
                        counter += 1
                    elif x != y and y != z and z != x:
                        counter += 6
                    else:
                        counter += 3

    return counter


if __name__ == '__main__':
    main()

#6 24 54 96
#1  4  9 16
#18

### FIXED CODE ###

#from matplotlib import pyplot as plt
def binary_search(mn,mx,a,x,y):
    #リストlからaの値のインデックスをサーチする。
    #二分探索を可能にするためにはリストlはソートされていなければならない。
    z = (mx+1)//2
    low = mn
    high = mx+1
    while low <= high:
        temp = rule2(x,y,z)
        if temp == a:
            if z <= 0:
                return None
            return z
        elif temp < a:
            low = z + 1
        elif temp > a:
            high = z - 1

        z = (low + high) // 2
    return None

def rule2(x,y,z):
    return x ** 2 + y ** 2 + z**2 + x * y + y * z + z*x
def main():
    n = int(input())
    x = []
    y = []
    for i in range(1,n+1):
        #x.append(i)
        #y.append(f(i))
        print(f(i))
    #plt.scatter(x,y)
    #plt.show()


def f(n):
    counter = 0
    for x in range(1,n):
        if x ** 2 > n:
            break
        for y in range(x,n-x**2):
            if y < x:
                continue
            if x ** 2 + y ** 2 > n:
                break
            z = binary_search(y,n-x**2-y**2-x*y,n,x,y)
            if z == None:
                continue
            else:
                if rule2(x,y,z) == n:
                    if x == y and y == z and z == x:
                        counter += 1
                    elif x != y and y != z and z != x:
                        counter += 6
                    else:
                        counter += 3

    return counter


if __name__ == '__main__':
    main()

#6 24 54 96
#1  4  9 16
#18
### BUGGY CODE ###

#D
from collections import defaultdict
n = int(input())
a = list(map(int,input().split()))
mp = defaultdict(int)
for i in a:
    mp[i] += 1
q = int(input())
for _ in range(q):
    #print(mp)
    s = 0   
    b,c=map(int,input().split())
    if c in mp:
        mp[c] = mp[c]+mp[b]
        mp.pop(b)
    elif b in mp:
        mp[c] = mp.pop(b)
        
    for i in mp:
        s += (mp[i])*i
    print(s)
    

### FIXED CODE ###

#D                 more faster method than above               see it ..........
l = lambda : list(map(int,input().strip().split()))
n = int(input())
a = l()
t = [0]*(10**5+1)
s = 0
for i in a:
    s += i
    t[i] += 1
q = int(input())
for _ in range(q):
    b,c = l()
    s += (c-b)*t[b]
    t[c] += t[b]
    t[b] = 0
    print(s)
### BUGGY CODE ###

import sys
imput=sys.stdin.readline
n,m=map(int,input().split())
l=[]
for _ in range(m):
    l.append(int(input()))
#print(l)
dp=[0]*(n+1)
dp[0]=1
if 1 not in l:
    dp[1]=1
 
for i in range(2,n+1):
    if i in l:
        dp[i]=0
    else:
        dp[i]=(dp[i-1]+dp[i-2])%(1000000007)
print(dp[-1])

### FIXED CODE ###

n,m=map(int,input().split())
a=[-1]
for i in range(m):
    s=int(input())
    a.append(s)  
a.append(n+1)
if 1 in a:
    a=a[1:]
if n-1 in a:
    a=a[:-1]
b=[]
for i in range(len(a)-1):
    b.append(a[i+1]-a[i]-2)
l=[1,1,2]
for i in range(3,n+1):
    l.append(l[i-2]+l[i-1])
ans=1
#print(a,b,l)
for i in range(len(b)):
    if b[i]<0:
        print(0)
        break
    else:
        ans*=l[b[i]]%1000000007
else:
    print(ans%1000000007)
### BUGGY CODE ###

S = list(input())
Q = int(input())

# hd = []
# bc = []
# cnt = 0

for i in range(Q):
    q = list(input().split())

    if q[0]=="1":
        S.reverse()
    else:
        f = int(q[1])
        c = list(q[2])

        if f%2==0:
            S = S+c
        else:
            S = c+S
    # print(S)


    # if q[0]=="1":
    #     hd,bc = bc,hd
    #     cnt += 1
    
    # elif q[0]=="2":
    #     f = int(q[1])
    #     c = q[2]

    #     if f%2==0:
    #         bc.append(c)
    #     else:
    #         hd.append(c)
    # print(hd,bc)

# ans = hd + S + bc

for i in range(len(S)):
    print(S[i],end="")
print()











### FIXED CODE ###

from collections import deque

S = list(input())
Q = int(input())

d = deque(S)

hd = []
bc = []
cnt = 0
mm = 0

for i in range(Q):
    q = list(input().split())

    if q[0]=="1":
        cnt += 1
    
# f:奇数 cnt:偶数 先頭    
# f:奇数 cnt:奇数 後方    
# f:偶数 cnt:偶数 後方
# f:奇数 cnt:偶数 先頭
#   
    elif q[0]=="2":
        f = int(q[1])
        c = q[2]
        mm += 1

        if (f+cnt)%2==0:
            d.append(c)
        else:
            d.appendleft(c)

if cnt%2==0:
    for i in range(len(S)+mm):
        # print(i,d)
        print(d.popleft(),end='')
else:
    for i in range(len(S)+mm):
        print(d.pop(),end='')
print()
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
cnt = 0

for i in range(n):
    for j in range(n):
        if i >= j:
            continue
        if abs((i+1) - (j+1)) == (a[i] + a[j]):
            cnt += 1
print(cnt)

### FIXED CODE ###

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

B = Counter(i + a for i, a in enumerate(A))
C = Counter(j - a for j, a in enumerate(A))
#print(B)
#print(C)
for k, v in B.items():
    cnt += C[k] * v
print(cnt)
### BUGGY CODE ###

#!/usr/bin/env python3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")
import sys
from functools import reduce
N,K = map(int,sys.stdin.readline().split())

A = tuple(map(int,sys.stdin.readline().split())) # single line with multi param

# cum = [1]*(N+1)
# for i in range(N):
#     cum[i+1] = cum[i]*A[i]
#     if K <= i:
#         cur = cum[i+1]//cum[i-K+1]
#         #print(i+1,cum[i],i-K,pre,cur)#
#         if pre < cur:
#             print("Yes")
#         else:
#             print("No")
#         pre = cur
#     else:
#         pre = cum[i+1]#

#print(cum)
# #https://qiita.com/keymoon/items/11fac5627672a6d6a9f6
# import sys
# T = sys.stdin.readline().rstrip()
# NT = len(T)
# P = sys.stdin.readline().rstrip()
# NP = len(P)
# if NT < NP:
#     exit()
# MOD = 2**61-1 #prime
# A = [ord(c) for c in T]
# pows = [1]*(NT+1)
# shash = [0]*(NT+1)
# for i in range(NT):
#     pows[i+1] = (pows[i]*126)%MOD
#     shash[i+1] = (shash[i]*126+A[i])%MOD
# ph = 0
# for i in range(NP):
#     ph = (ph*126+ord(P[i]))%MOD
# for i in range(len(T)-NP+1):
#     if ph == (shash[i+NP]-shash[i]*pows[NP])%MOD:
#         print(i)

pre = reduce((lambda x, y: x * y), [A[i] for i in range(K)])
for i in range(K,N):
    #print(i)
    cur = (pre//A[i-K])*A[i]
    if pre < cur:
        print("Yes")
    else:
        print("No")
    pre = cur


### FIXED CODE ###

#!/usr/bin/env python3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")
import sys
from functools import reduce
N,K = map(int,sys.stdin.readline().split())

A = tuple(map(int,sys.stdin.readline().split())) # single line with multi param

#pre = reduce((lambda x, y: x * y), [A[i] for i in range(K)])
for i in range(K,N):
    #print(i)
    # cur = (pre//A[i-K])*A[i]
    if A[i-K] < A[i]:
        print("Yes")
    else:
        print("No")
    # if pre < cur:
    #
    # else:
    #     print("No")
    # pre = cur
### BUGGY CODE ###

def main():
    from collections import Counter
    import sys
    input = sys.stdin.buffer.readline

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

    ans = 0
    A.sort(reverse=True)
    c = Counter(A)

    for b in A:
        a = (2**b.bit_length()) - b
        if a == b:
            ans += c[b]//2
            c[b] %= 2
        else:
            if a in c.keys():
                cur = min(c[a], c[b])
                ans += cur
                c[b] -= cur
                c[a] -= cur
        # print(a, b, c, ans)

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from collections import Counter
    import sys
    input = sys.stdin.buffer.readline

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

    ans = 0
    A.sort(reverse=True)
    c = Counter(A)

    for b in A:
        if c[b] == 0:
            continue
        a = (2 ** b.bit_length()) - b
        if a == b:
            cur = c[b]//2
        else:
            cur = min(c[a], c[b])
        ans += cur
        c[b] -= cur
        c[a] -= cur
        # print(a, b, c, ans)

    print(ans)


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

def main():
    INF = float('inf')
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    maxA = max(A for A,B in AB)
    dp = [INF]*(H+maxA+1)
    dp[0] = 0
    for i in range(1,H+maxA):
        dp[i] = min(dp[i-A]+B for A,B in AB)
    print(min(dp[H:]))


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    maxA = max(A for A,B in AB)
    dp = [0]*(H+maxA)
    for i in range(0,H+maxA):
        if i <= 0:
            dp[i] = 0
        else:
            dp[i] = min(dp[i-A]+B for A,B in AB)
    print(min(dp[H:]))


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

from collections import deque
n = int(input())
Ps = list(map(lambda x: int(x)-1, input().split()))
cost = [min(min(i, n-1-i), min(j, n-1-j)) for i in range(n) for j in range(n)]
DIRC = [(-1, 0), (0, 1), (1, 0), (0, -1)]
exist = [1]*(n**2)


def to_idx(p):
    i, j = divmod(p, n)
    return i, j


def to_v(i, j):
    return i*n+j


def bfs(init_v):
    next_v = deque([to_idx(init_v)])
    exist[init_v] = 0
    while next_v:
        i, j = next_v.popleft()

        for di, dj in DIRC:
            x, y = i+di, j+dj
            if x < 0 or y < 0 or n <= x or n <= y:
                continue

            if cost[to_v(x, y)] <= cost[to_v(i, j)]+exist[to_v(i, j)]:
                continue
            cost[to_v(x, y)] = cost[to_v(i, j)]+exist[to_v(i, j)]
            next_v.append((x, y))


ans = 0
for p in Ps:
    ans += cost[p]
    bfs(p)
print(ans)

### FIXED CODE ###

from collections import deque
n = int(input())
Ps = list(map(lambda x: int(x)-1, input().split()))
cost = [min(i, n-1-i, j, n-1-j) for i in range(n) for j in range(n)]
exist = [1]*(n**2)


def to_idx(p):
    return divmod(p, n)


def to_v(i, j):
    return i*n+j


def bfs(init_v):
    next_v = deque([init_v])
    exist[init_v] = 0
    while next_v:
        v = next_v.popleft()
        i, j = to_idx(v)
        if 0 < i:
            v2 = v-n
            if cost[v2] > cost[v]+exist[v]:
                cost[v2] = cost[v]+exist[v]
                next_v.append(v2)

        if i < n-1:
            v2 = v+n
            if cost[v2] > cost[v]+exist[v]:
                cost[v2] = cost[v]+exist[v]
                next_v.append(v2)

        if 0 < j:
            v2 = v-1
            if cost[v2] > cost[v]+exist[v]:
                cost[v2] = cost[v]+exist[v]
                next_v.append(v2)

        if j < n-1:
            v2 = v+1
            if cost[v2] > cost[v]+exist[v]:
                cost[v2] = cost[v]+exist[v]
                next_v.append(v2)

ans = 0
for p in Ps:
    ans += cost[p]
    bfs(p)
print(ans)
### BUGGY CODE ###

import numpy as np


n = int(input())
a = [2*int(_) for _ in input().split()]
s = []
for i in range(n):
    l = [0 for _ in range(n)]
    l[i] = 1
    if i+1 != n:
        l[i+1] = 1
    else:
        l[0] = 1
    s.append(l)
A = np.array(s)
b = np.array(a)
Ainv = np.linalg.inv(A)
x = np.dot(Ainv, b)
for i in range(len(x)):
    print(int(x[i]))

### FIXED CODE ###

n = int(input())
a = [2*int(_) for _ in input().split()]
t = a[-1]
x = [0 for _ in range(n)]
for i in range(-2, -n-1, -1):
    t = a[i] - t
x[0] = t // 2
for i in range(0, n-1):
    x[i+1] = a[i] - x[i]
for i in range(len(x)):
    print(x[i])
### BUGGY CODE ###

import sys
# import math
import itertools
# import functools
import operator

def resolve(in_):
    N = int(next(in_))
    A = tuple(map(int, next(in_).split()))

    max_a = max(A)
    temp = [0] * (max_a + 1)
    temp[1] = 1

    for i in range(2, max_a + 1):
        if temp[i]:
            continue

        j = i
        while j < max_a + 1:
            if not temp[j]:
                temp[j] = i
            j += i

    B = []
    for a in A:
        s = set()
        while a > 1:
            s.add(temp[a])
            a = a // temp[a]
        B.append(s)
    
    C = tuple(filter(lambda x: x > 1, itertools.chain.from_iterable(B)))
    D = frozenset(C)
    if len(C) == len(D):
        return 'pairwise coprime'

    # if functools.reduce(math.gcd, A) == 1:
    # v = tuple(itertools.accumulate(B, operator.and_))
    if not all(itertools.accumulate(B, operator.and_)):
        return 'setwise coprime'

    return 'not coprime'
    

def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import math
import functools

def resolve(in_):
    N = int(next(in_))
    A = tuple(map(int, next(in_).split()))

    max_a = max(A)
    temp = [0] * (max_a + 1)
    temp[1] = 1

    for i in range(2, max_a + 1):
        if temp[i]:
            continue

        j = i
        while j < max_a + 1:
            if not temp[j]:
                temp[j] = i
            j += i

    B = set()
    for a in A:
        s = set()
        while a > 1:
            s.add(temp[a])
            a = a // temp[a]
        for v in s:
            if v in B:
                if functools.reduce(math.gcd, A) == 1:
                    return 'setwise coprime'
                else:
                    return 'not coprime'
            B.add(v)
    
    return 'pairwise coprime'
    

def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


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

from bisect import *
A,B,Q=map(int,input().split())
S=[int(input()) for i in range(A)]
T=[int(input()) for i in range(B)]
value1=2*(10**10)
for zzz in range(Q):
    x=int(input())
    value=value1

    s1=bisect_left(S,x)
    for s in [s1-1,s1]:
        if 0<= s < A:
            t1=bisect_left(T,S[s])
            for t in [t1-1,t1]:
                a=0
                if 0<= t < B:
                    if x>S[s]:
                        a+=x-S[s]
                    else:
                        a+=S[s]-x
                    if S[s]>T[t]:
                        a+=S[s]-T[t]
                    else:
                        a+=T[t]-S[s]
                    if value>a:
                        value=a
    t1=bisect_left(T,x)
    for t in [t1-1,t1]:
        if 0<= t < B:
            s1=bisect_left(S,T[t])
            for s in [s1-1,s1]:
                a=0
                if 0<= s < A:
                    if x>T[t]:
                        a+=x-T[t]
                    else:
                        a+=T[t]-x
                    if S[s]>T[t]:
                        a+=S[s]-T[t]
                    else:
                        a+=T[t]-S[s]
                    if value>a:
                        value=a

    print(value)


### FIXED CODE ###

from bisect import *
A,B,Q=map(int,input().split())
S=[int(input()) for i in range(A)]
T=[int(input()) for i in range(B)]
X=[int(input()) for i in range(Q)]
value1=2*(10**10)
for x in X:
    value=value1
    s1=bisect_left(S,x)
    for s in [s1-1,s1]:
        if -1< s < A:
            t1=bisect_left(T,S[s])
            for t in [t1-1,t1]:
                a=0
                if -1< t < B:
                    if x>S[s]:
                        a+=x-S[s]
                    else:
                        a+=S[s]-x
                    if S[s]>T[t]:
                        a+=S[s]-T[t]
                    else:
                        a+=T[t]-S[s]
                    if value>a:
                        value=a
    t1=bisect_left(T,x)
    for t in [t1-1,t1]:
        if -1< t < B:
            s1=bisect_left(S,T[t])
            for s in [s1-1,s1]:
                a=0
                if -1< s < A:
                    if x>T[t]:
                        a+=x-T[t]
                    else:
                        a+=T[t]-x
                    if S[s]>T[t]:
                        a+=S[s]-T[t]
                    else:
                        a+=T[t]-S[s]
                    if value>a:
                        value=a

    print(value)
### BUGGY CODE ###

import sys

a = []
b = []
for line in sys.stdin:
    a.append(int(line))
    b.append(int(line))

del a[0]
del a[len(a)-1]
del b[0]
del b[0]

list = []
for i in range(len(a)):
    for j in range(len(b)):
        if j >= i:
            sub = b[j]-a[i]
            list.append(sub)
print(max (list))


### FIXED CODE ###

import sys

a = []
b = []
for line in sys.stdin:
    a.append(int(line))
    b.append(int(line))

del a[0]
del a[len(a)-1]
del b[0]
del b[0]

maxv = -1000000000
minv = a[0]
for i in range(len(a)):
    maxv = max(maxv,b[i]-minv)
    minv = min(minv,b[i])
print(maxv)
### BUGGY CODE ###

N=input()
a=list(map(int, input().split()))
ans=1
for v in a:
	ans*=v
if 1000000000000000000 < ans:
	ans = -1
print(ans)


### FIXED CODE ###

N=input()
a=list(map(int, input().split()))
#print(a)
ans=1
for v in a:
	ans*=v
	if 1000000000000000000 < ans:
		ans = -1
		break
if any([v==0 for v in a]):
	ans=0
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)
N=int(input())
xy=[list(map(int,input().split()))+[i] for i in range(N)]
xy.sort()
path = []

def get_par(n):
    if par[n] is None:return n
    return get_par(par[n])

def same(i,j):
    return get_par(i) == get_par(j)

def unite(i,j):
    j = get_par(j)
    par[j] = get_par(i)
    return

for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    if i>j:i,j = j,i
    path.append((abs(x-x2),i,j))
xy.sort(key=lambda x:x[1])
for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    if i>j:i,j = j,i
    path.append((abs(y-y2),i,j))
path.sort(key = lambda x:x[0],reverse=True)
par = [None]*N
cnt = 0
ans = 0
while cnt < N-1:
    c,i,j = path.pop()
    if same(i,j):continue
    unite(i,j)
    ans += c
    cnt += 1
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
N=int(input())
xy=[list(map(int,input().split()))+[i] for i in range(N)]
xy.sort()
path = []

def get_par(n):
    if par[n] is None:return n
    par[n] = get_par(par[n])
    return par[n]

def same(i,j):
    return get_par(i) == get_par(j)

def unite(i,j):
    j = get_par(j)
    par[j] = get_par(i)
    return

for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    path.append((abs(x-x2),i,j))
xy.sort(key=lambda x:x[1])
for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    path.append((abs(y-y2),i,j))
path.sort(key = lambda x:x[0],reverse=True)
par = [None]*N
cnt = 0
ans = 0
while cnt < N-1:
    c,i,j = path.pop()
    if same(i,j):continue
    unite(i,j)
    ans += c
    cnt += 1
print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
cnt=0
for i in range(n-1):
  for j in range(max(i+1,a[i]+1),n):
    if abs(i-j)==a[i]+a[j]:
      cnt+=1
print(cnt)

### FIXED CODE ###

from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))
d=defaultdict(int)
cnt=0
for i in range(n):
  cnt+=d[i-a[i]]
  d[a[i]+i]+=1
print(cnt)
### BUGGY CODE ###

S = str(input())
slist = list(S)
L = len(slist)
count = 0
fcount = 0
i = 0
while i < L:
    if i < L-1 and slist[i] == "B" and slist[i+1] == "W":
        slist[i],slist[i+1] = slist[i+1],slist[i]
        count+=1
        fcount+=1
        i+=1
    elif i == L-1:
        if fcount == 0:
            break
        else:
            i = 0
            fcount = 0
    else:
        i+=1
print(count)

### FIXED CODE ###

S = str(input())
slist = list(S)
L = len(slist)
count = 0
fcount = 0
for i in range(L):
  if slist[i] == "W":
    count+=(i-fcount)
    fcount+=1
print(count)
### BUGGY CODE ###

import sys

input = sys.stdin.readline
n = int(input())
al = list(map(int,input().split()))

from collections import defaultdict
G = defaultdict(list)

for _ in range(n-1):
    u,v = map(int,input().split())
    G[u-1].append(v-1)
    G[v-1].append(u-1)

from bisect import bisect
ansl = [0 for i in range(n)]
dp = [float("inf") for _ in range(n+1)]
dp[0] = -1
used = [0 for i in range(n)]
used[0] = 1

stack = []
def dfs(pos, dp):
    idx = bisect(dp, al[pos] - 1)
    stack.append((idx, dp[idx]))
    dp[idx] = min(al[pos], dp[idx])
    ansl[pos] = max(i for i in range(n+1) if dp[i] < float("inf"))
    for v in G[pos]:
        if used[v] == 0:
            used[v] = 1
            dfs(v, dp)
            idx, k= stack.pop()
            dp[idx] = k


dfs(0, dp)
flag = False
for i in range(n):
    print(ansl[i])




### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

import sys
input = sys.stdin.readline

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

from collections import defaultdict
G = defaultdict(list)

for _ in range(n-1):
    u,v = map(int,input().split())
    G[u-1].append(v-1)
    G[v-1].append(u-1)

from bisect import bisect
ansl = [0 for i in range(n)]
dp = [float("inf") for _ in range(n+1)]
dp[0] = -1
used = [0 for i in range(n)]
used[0] = 1


stack = []
def dfs(pos):
    idx = bisect(dp, al[pos] - 1)
    stack.append((idx, dp[idx]))
    dp[idx] = min(al[pos], dp[idx])
    ansl[pos] = bisect(dp, 10**18) - 1
    for v in G[pos]:
        if used[v] == 0:
            used[v] = 1
            dfs(v)
            idx, k = stack.pop()
            dp[idx] = k


dfs(0)
flag = False
for i in range(n):
    print(ansl[i])
### BUGGY CODE ###

import itertools
n = int(input())
sl = []
for _ in range(n):
    sl.append(int(input()))

ans = 0
for i in range(1,n+1):
    for v in itertools.combinations(sl,i):
       if sum(v) % 10 != 0:
        ans = max(ans, sum(v))
print(ans)

### FIXED CODE ###

import itertools
n = int(input())
sl = []
for _ in range(n):
    sl.append(int(input()))

if sum(sl) % 10 != 0:
    print(sum(sl))
    exit()

ans = 0
for v in itertools.combinations(sl,n-1):
   if sum(v) % 10 != 0:
    ans = max(ans, sum(v))
print(ans)