CodeEff/ECCO huggingface dataset:
# Original solution
# 木によってLISを作り、dfsで抜けるときにLISをその前の状態まで復元する

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina1(x):
    return int(x) - 1


def read_ints(mina=False):
    if mina:
        return list(map(mina1, read().split()))
    else:
        return list(map(int, read().split()))


def read_a_int():
    return int(read())


from bisect import bisect_left, bisect_right

####################
# dp = []
# for a in A:
#     print(dp)
#     idx = bisect_left(dp, a)  # 初めて真に大きい要素になるidx
#     if idx == len(dp):
#         dp.append(a)
#     else:
#         dp[idx] = a  # aに更新
# print(dp)
# print(len(dp))
####################

from collections import defaultdict
N = read_a_int()
A = read_ints()
tree = defaultdict(lambda: [])
for _ in ra(N - 1):
    u, v = read_ints(mina=True)
    tree[u].append(v)
    tree[v].append(u)

LIS = []
ans = [0] * N  # 各ノードのlen(LIS)を記録


def dfs(now, p):  # 現在のノード、親
    # 終了条件# 子が無いとき

    # LISの更新
    idx = bisect_left(LIS, A[now])
    is_append = False
    if idx == len(LIS):
        LIS.append(A[now])
        is_append = True
    else:
        old = LIS[idx]   # なんの値だったか持っておく
        LIS[idx] = A[now]  # aに更新
    ans[now] = len(LIS)  # 答えを記録

    # 次のノードを探索
    for to in tree[now]:
        if to == p:
            continue
        dfs(to, now)
    # 抜けるときにLISを復元
    if is_append:
        del LIS[idx]
    else:
        LIS[idx] = old


dfs(0, -1)
print(*ans, sep='\n')


# Optimized solution
# 木によってLISを作り、dfsで抜けるときにLISをその前の状態まで復元する

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina1(x):
    return int(x) - 1


def read_ints(mina=False):
    if mina:
        return list(map(mina1, read().split()))
    else:
        return list(map(int, read().split()))


def read_a_int():
    return int(read())


from bisect import bisect_left, bisect_right
from collections import defaultdict
N = read_a_int()
A = read_ints()
tree = defaultdict(lambda: [])
for _ in ra(N - 1):
    u, v = read_ints(mina=True)
    tree[u].append(v)
    tree[v].append(u)

LIS = []
ans = [0] * N  # 各ノードのlen(LIS)を記録


def dfs(now, p):  # 現在のノード、親
    a = A[now]
    # LISの更新
    idx = bisect_left(LIS, a)
    is_append = False
    if idx == len(LIS):
        LIS.append(a)
        is_append = True
    else:
        old = LIS[idx]   # なんの値だったか持っておく
        LIS[idx] = a  # aに更新

    ans[now] = len(LIS)  # 答えを記録
    # 次のノードを探索
    for to in tree[now]:
        if to == p:
            continue
        dfs(to, now)

    # 抜けるときにLISを復元
    if is_append:
        del LIS[idx]
    else:
        LIS[idx] = old


dfs(0, -1)
print(*ans, sep='\n')
# Original solution
# 木によってLISを作り、dfsで抜けるときにLISをその前の状態まで復元する

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina1(x):
    return int(x) - 1


def read_ints(mina=None):
    ret = map(int, read().split())
    if mina == None:
        return list(ret)
    else:
        return list(map(lambda x: x - mina, ret))


def read_a_int():
    return int(read())


from bisect import bisect_left, bisect_right
from collections import defaultdict
N = read_a_int()
A = read_ints()
tree = defaultdict(lambda: [])
for _ in ra(N - 1):
    u, v = read_ints(mina=1)
    tree[u].append(v)
    tree[v].append(u)

LIS = []
ans = [0] * N  # 各ノードのlen(LIS)を記録


def dfs(now, p):  # 現在のノード、親
    a = A[now]
    # LISの更新
    idx = bisect_left(LIS, a)
    is_append = False
    if idx == len(LIS):
        LIS.append(a)
        is_append = True
    else:
        old = LIS[idx]   # なんの値だったか持っておく
        LIS[idx] = a  # aに更新

    ans[now] = len(LIS)  # 答えを記録
    # 次のノードを探索
    for to in tree[now]:
        if to == p:
            continue
        dfs(to, now)

    # 抜けるときにLISを復元
    if is_append:
        del LIS[idx]
    else:
        LIS[idx] = old


dfs(0, -1)
print(*ans, sep='\n')


# Optimized solution
# 木によってLISを作り、dfsで抜けるときにLISをその前の状態まで復元する

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina1(x):
    return int(x) - 1


def read_ints(mina=None):
    ret = map(int, read().split())
    if mina == None:
        return list(ret)
    else:
        return list(map(lambda x: x - 1, ret))


def read_a_int():
    return int(read())


from bisect import bisect_left, bisect_right
from collections import defaultdict
N = read_a_int()
A = read_ints()
tree = defaultdict(lambda: [])
for _ in ra(N - 1):
    u, v = read_ints(mina=1)
    tree[u].append(v)
    tree[v].append(u)

LIS = []
ans = [0] * N  # 各ノードのlen(LIS)を記録


def dfs(now, p):  # 現在のノード、親
    a = A[now]
    # LISの更新
    idx = bisect_left(LIS, a)
    is_append = False
    if idx == len(LIS):
        LIS.append(a)
        is_append = True
    else:
        old = LIS[idx]   # なんの値だったか持っておく
        LIS[idx] = a  # aに更新

    ans[now] = len(LIS)  # 答えを記録
    # 次のノードを探索
    for to in tree[now]:
        if to == p:
            continue
        dfs(to, now)

    # 抜けるときにLISを復元
    if is_append:
        del LIS[idx]
    else:
        LIS[idx] = old


dfs(0, -1)
print(*ans, sep='\n')
# Original solution
# 木によってLISを作り、dfsで抜けるときにLISをその前の状態まで復元する

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina1(x):
    return int(x) - 1


def read_ints(mina=None):
    ret = map(int, read().split())
    if mina == None:
        return list(ret)
    else:
        return list(map(mina1, ret))


def read_a_int():
    return int(read())


from bisect import bisect_left, bisect_right
from collections import defaultdict
N = read_a_int()
A = read_ints()
tree = defaultdict(lambda: [])
for _ in ra(N - 1):
    u, v = read_ints(mina=1)
    tree[u].append(v)
    tree[v].append(u)

LIS = []
ans = [0] * N  # 各ノードのlen(LIS)を記録


def dfs(now, p):  # 現在のノード、親
    a = A[now]
    # LISの更新
    idx = bisect_left(LIS, a)
    is_append = False
    if idx == len(LIS):
        LIS.append(a)
        is_append = True
    else:
        old = LIS[idx]   # なんの値だったか持っておく
        LIS[idx] = a  # aに更新

    ans[now] = len(LIS)  # 答えを記録
    # 次のノードを探索
    for to in tree[now]:
        if to == p:
            continue
        dfs(to, now)

    # 抜けるときにLISを復元
    if is_append:
        del LIS[idx]
    else:
        LIS[idx] = old


dfs(0, -1)
print(*ans, sep='\n')


# Optimized solution
# 木によってLISを作り、dfsで抜けるときにLISをその前の状態まで復元する

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina1(x): return int(x) - 1


def read_ints(tozero=False):
    if tozero == False:
        return list(map(int, read().split()))
    else:
        return list(map(mina1, read().split()))


def read_a_int():
    return int(read())


from bisect import bisect_left, bisect_right
from collections import defaultdict
N = read_a_int()
A = read_ints()
tree = defaultdict(lambda: [])
for _ in ra(N - 1):
    u, v = read_ints(True)
    tree[u].append(v)
    tree[v].append(u)

LIS = []
ans = [0] * N  # 各ノードのlen(LIS)を記録


def dfs(now, p):  # 現在のノード、親
    a = A[now]
    # LISの更新
    idx = bisect_left(LIS, a)
    is_append = False
    if idx == len(LIS):
        LIS.append(a)
        is_append = True
    else:
        old = LIS[idx]   # なんの値だったか持っておく
        LIS[idx] = a  # aに更新

    ans[now] = len(LIS)  # 答えを記録
    # 次のノードを探索
    for to in tree[now]:
        if to == p:
            continue
        dfs(to, now)

    # 抜けるときにLISを復元
    if is_append:
        del LIS[idx]
    else:
        LIS[idx] = old


dfs(0, -1)
print(*ans, sep='\n')
# Original solution
#!/usr/bin/env python3
#F

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
edges = [[] for _ in range(n)]
for _ in range(n-1):
    u, v = LI()
    edges[u-1].append(v-1)
    edges[v-1].append(u-1)

dp = [inf]*n
ans = [None]*n
ans[0] = 1
dp[0] = a[0]
def dfs(s, p, dp, num):
    for u in edges[s]:
        flag = False
        if u == p:
            continue
        r = bl(dp, a[u])
        tmp = dp[r]
        if dp[r] == inf:
            num += 1
            flag = True
        ans[u] = num
        dp[r] = min(dp[r], a[u])
        dfs(u, s, dp, num)
        dp[r] = tmp
        if flag:
            num -= 1
    return
dfs(0, -1, dp, 1)

for i in ans:
    print(i)
        

# Optimized solution
#!/usr/bin/env python3
#F

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
edges = [[] for _ in range(n)]
for _ in range(n-1):
    u, v = LI()
    edges[u-1].append(v-1)
    edges[v-1].append(u-1)

dp = [inf]*n
ans = [None]*n
ans[0] = 1
dp[0] = a[0]
def dfs(s, p, dp, num):
    for u in edges[s]:
        flag = False
        if u == p:
            continue
        if ans[u] != None:
            continue
        r = bl(dp, a[u])
        tmp = dp[r]
        if dp[r] == inf:
            num += 1
            flag = True
        ans[u] = num
        dp[r] = min(dp[r], a[u])
        dfs(u, s, dp, num)
        dp[r] = tmp
        if flag:
            num -= 1
    return
dfs(0, -1, dp, 1)

for i in ans:
    print(i)
# Original solution
import sys
sys.setrecursionlimit(10 ** 9)

from bisect import bisect_left

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

G = [[] for _ in range(N)]

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

root = 0
stack = [root]
visited = set()
visited.add(root)
done = set()
vs = []

ans = [0] * N
memo = [None] * N
memo[root] = (0, A[root])

INF = 10 ** 10
dp = [INF] * N

while stack:
    now_ = stack[-1]
    if now_ in done:
        j, a = memo[now_]
        dp[j] = a
        stack.pop()
        vs.append(now_)
    else:
        for next_ in G[now_][::-1]:
            if next_ in visited:
                continue
            visited.add(next_)
            stack.append(next_)
        done.add(now_)

        tmp = bisect_left(dp, A[now_])
        memo[now_] = (tmp, dp[tmp])
        dp[tmp] = A[now_]
        ans[now_] = bisect_left(dp, INF)

# print (vs)
print (*ans, sep = '\n')


# Optimized solution
def main():
    import sys
    input = sys.stdin.readline

    from bisect import bisect_left

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

    G = [[] for _ in range(N)]

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

    root = 0
    stack = [root]
    visited = set()
    visited.add(root)
    done = set()
    vs = []

    ans = [0] * N
    memo = [None] * N
    memo[root] = (0, A[root])

    INF = 10 ** 10
    dp = [INF] * N

    while stack:
        now_ = stack[-1]
        if now_ in done:
            j, a = memo[now_]
            dp[j] = a
            stack.pop()
            vs.append(now_)
        else:
            for next_ in G[now_][::-1]:
                if next_ in visited:
                    continue
                visited.add(next_)
                stack.append(next_)
            done.add(now_)

            tmp = bisect_left(dp, A[now_])
            memo[now_] = (tmp, dp[tmp])
            dp[tmp] = A[now_]
            ans[now_] = bisect_left(dp, INF)

    # print (vs)
    print (*ans, sep = '\n')

if __name__ == '__main__':
    main()
# Original solution
def main():
    import sys
    input = sys.stdin.readline
    import bisect
    from collections import deque
    from copy import deepcopy

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


    ans = [[] for i in range(n)]
    ans[0] = [[l[0]],1]
    q = deque([])
    q.append((0,-1))
    while q:
        now,bef = q.popleft()

        for nex in e[now]:
            if nex != bef:
                a = l[nex]
                b = ans[now][1]
                
                c = deepcopy(ans[now][0])
                if a > c[-1]:
                        c.append(l[nex])
                        ans[nex] = [c,b+1]
                else:
                    c[bisect.bisect_left(c, l[nex])] = l[nex]
                    ans[nex] = [c,b]
                q.append((nex,now))

    
    for i in ans:
        print((i[1]))
if __name__ == "__main__":
    main()

# Optimized solution

import sys
input = sys.stdin.readline
import bisect

sys.setrecursionlimit(10**7)
n = int(eval(input()))
l = list(map(int,input().split()))
e = [[] for i in range(n)]
for i in range(n-1):
    a,b = list(map(int,input().split()))
    a -= 1
    b -= 1
    e[a].append(b)
    e[b].append(a)


ans = [0]*n
ans[0] = 1
dp = [l[0]]

def dfs(now,bef):
    
    change = True
    if l[now] > dp[-1]:
        dp.append(l[now])
    else:
        index = bisect.bisect_left(dp,l[now])
        change = False
        s = dp[index]
        dp[index] = l[now] 
    ans[now] = len(dp)
    
    for nex in e[now]:
        if nex != bef:
            dfs(nex,now)
    if change:
        dp.pop()
    else:
        dp[index] = s 

for i in e[0]:
    dfs(i,0)

for i in ans:
    print(i)
# Original solution
import bisect
import sys
sys.setrecursionlimit(10**8)


n = int(eval(input()))
A = list(map(int, input().split()))

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


DP = [10**9+7] * (n+1)
DP[0] = 0
ans = [0] * n


def dfs(node):
    node = node
    num = A[node]
    update_idx = bisect.bisect_left(DP, num)
    prev = DP[update_idx]
    DP[update_idx] = num
    lis = bisect.bisect_left(DP, 10**9+1) - 1
    ans[node] = lis
    for nex in edges[node]:
        if not ans[nex]:
            dfs(nex)

    DP[update_idx] = prev


dfs(0)
for res in ans:
    print(res)


# Optimized solution
import bisect


n = int(eval(input()))
A = list(map(int, input().split()))

edges = [[] for _ in range(n+1)]
for _ in range(n-1):
    from_, to = list(map(int, input().split()))
    edges[from_].append(to)
    edges[to].append(from_)


DP = [10**9+7] * (n+1)
limit = 10**9 + 1
DP[0] = 0
olds = [None] * (n+1)
ans = [0] * n

todo = [1]
while todo:
    node = todo.pop()
    if node > 0:
        num = A[node-1]
        update_idx = bisect.bisect_left(DP, num)
        old = DP[update_idx]
        olds[node] = (old, update_idx)
        DP[update_idx] = num
        lis = bisect.bisect_left(DP, limit) - 1
        ans[node-1] = lis

        todo.append(-node)
        for to in edges[node]:
            if ans[to-1]:
                continue
            todo.append(to)

    else:
        node = -node
        old, update_idx = olds[node]
        DP[update_idx] = old

for res in ans:
    print(res)
# Original solution
import bisect


n = int(eval(input()))
A = list(map(int, input().split()))

edges = [[] for _ in range(n+1)]
for _ in range(n-1):
    from_, to = list(map(int, input().split()))
    edges[from_].append(to)
    edges[to].append(from_)


DP = [10**9+7] * (n+1)
limit = 10**9 + 1
DP[0] = 0
olds = [None] * (n+1)
ans = [0] * n

todo = [1]
while todo:
    node = todo.pop()
    if node > 0:
        num = A[node-1]
        update_idx = bisect.bisect_left(DP, num)
        old = DP[update_idx]
        olds[node] = (old, update_idx)
        DP[update_idx] = num
        lis = bisect.bisect_left(DP, limit) - 1
        ans[node-1] = lis

        todo.append(-node)
        for to in edges[node]:
            if ans[to-1]:
                continue
            todo.append(to)

    else:
        node = -node
        old, update_idx = olds[node]
        DP[update_idx] = old

for res in ans:
    print(res)


# Optimized solution
import bisect
import sys
input = sys.stdin.readline


n = int(eval(input()))
A = list(map(int, input().split()))

edges = [[] for _ in range(n+1)]
for _ in range(n-1):
    from_, to = list(map(int, input().split()))
    edges[from_].append(to)
    edges[to].append(from_)


DP = [10**9+7] * (n+1)
limit = 10**9 + 1
DP[0] = 0
olds = [None] * (n+1)
ans = [0] * n

todo = [1]
while todo:
    node = todo.pop()
    if node > 0:
        num = A[node-1]
        update_idx = bisect.bisect_left(DP, num)
        old = DP[update_idx]
        olds[node] = (old, update_idx)
        DP[update_idx] = num
        lis = bisect.bisect_left(DP, limit) - 1
        ans[node-1] = lis

        todo.append(-node)
        for to in edges[node]:
            if ans[to-1]:
                continue
            todo.append(to)

    else:
        node = -node
        old, update_idx = olds[node]
        DP[update_idx] = old

for res in ans:
    print(res)
# Original solution
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**5+10)
#input = sys.stdin.readline
from bisect import bisect_left

def dfs(i,before):
    global seq
    global ans
    added  = 0

    #現在地のAの値を、以前までのseqリストのどこに追加するか決める
    pos = bisect_left(seq,a[i-1])
    old = seq[pos]
    seq[pos]=a[i-1]
    ans[i-1]=bisect_left(seq,INF)

    #隣接する頂点に関して再帰
    for u in to[i]:
        if u==before:
            continue
        dfs(u,i)

    #seq配列をもとに戻す
    seq[pos]=old


N = I()
a = LI()
to = [[] for i in range(N+1)]
to[0] += [1]
for i in range(N-1):
    u,v = MI()
    to[u].append(v)
    to[v].append(u)
seq = [INF]*N
ans = [-1]*N

dfs(1,-1)
[print(i) for i in ans]


# Optimized solution
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)
#input = sys.stdin.readline
from bisect import bisect_left

def dfs(i,before):
    global seq
    global ans
    added  = 0

    #現在地のAの値を、以前までのseqリストのどこに追加するか決める
    pos = bisect_left(seq,a[i-1])
    old = seq[pos]
    seq[pos]=a[i-1]
    ans[i-1]=bisect_left(seq,INF)

    #隣接する頂点に関して再帰
    for u in to[i]:
        if u==before:
            continue
        dfs(u,i)

    #seq配列をもとに戻す
    seq[pos]=old


N = I()
a = LI()
to = [[] for i in range(N+1)]
to[0] += [1]
for i in range(N-1):
    u,v = MI()
    to[u].append(v)
    to[v].append(u)
seq = [INF]*N
ans = [-1]*N

dfs(1,-1)
[print(i) for i in ans]
# Original solution
#!/usr/bin/python3

import sys
from bisect import bisect_left

sys.setrecursionlimit(1000000)

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

nbs = [ [] for _ in range(n) ]

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


mlen =  [ 0 ] * n
dp = [ float('inf') ] * n

def getmlen(cur, p, ctail):
    idx = bisect_left(dp, a[cur])
    ov = dp[idx]
    if ctail < idx:
        ctail = idx

    dp[idx] = a[cur]
    mlen[cur] = ctail + 1
    
    for ch in nbs[cur]:
        if ch == p:
            continue

        getmlen(ch, cur, ctail)
    dp[idx] = ov

getmlen(0, -1, 0)

for i in range(n):
    print((mlen[i]))


# Optimized solution
#!/usr/bin/python3

import sys
from bisect import bisect_left

sys.setrecursionlimit(1000000)

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

nbs = [ [] for _ in range(n) ]

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


mlen =  [ 0 ] * n
dp = [ float('inf') ] * n

def getmlen(cur, p, ctail):
    for ch in nbs[cur]:
        if ch == p:
            continue

        idx = bisect_left(dp, a[ch])
        ov = dp[idx]

        ntail = max(ctail, idx)
        dp[idx] = a[ch]
        mlen[ch] = ntail + 1
        getmlen(ch, cur, ntail)
        dp[idx] = ov

        

dp[0] = a[0]
mlen[0] = 1
getmlen(0, -1, 0)

for i in range(n):
    print((mlen[i]))
# Original solution
#!/usr/bin/python3

import sys
from bisect import bisect_left

sys.setrecursionlimit(1000000)

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

nbs = [ [] for _ in range(n) ]

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


mlen =  [ 0 ] * n
dp = [ float('inf') ] * n

def getmlen(cur, p, ctail):
    for ch in nbs[cur]:
        if ch == p:
            continue

        idx = bisect_left(dp, a[ch])
        ov = dp[idx]

        ntail = max(ctail, idx)
        dp[idx] = a[ch]
        mlen[ch] = ntail + 1
        getmlen(ch, cur, ntail)
        dp[idx] = ov

        

dp[0] = a[0]
mlen[0] = 1
getmlen(0, -1, 0)

for i in range(n):
    print((mlen[i]))


# Optimized solution
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from bisect import bisect_left
 
N = int(eval(input()))
a = [int(i) for i in input().split()]
vec = [[] for _ in range(N)]
for _ in range(N - 1) :
  u, v = list(map(int, input().split()))
  vec[u - 1].append(v - 1)
  vec[v - 1].append(u - 1)
 
lis = [a[0]]
ret = [0] * N
def dfs(cur, pre) :
  for nex in vec[cur] :
    if nex == pre : continue
    if a[nex] > lis[-1] :
      lis.append(a[nex])
      ret[nex] = len(lis)
      dfs(nex, cur)
      lis.pop()
    else :
      pos = bisect_left(lis, a[nex])
      v = lis[pos]
      lis[pos] = a[nex]
      ret[nex] = len(lis)
      dfs(nex, cur)
      lis[pos] = v
 
dfs(0, -1)
 
ret[0] = 1
for i in range(N) :
  print((ret[i]))