CodeEff/ECCO huggingface dataset:
# Original solution
#!/usr/bin/python3

import sys
from bisect import bisect_left

sys.setrecursionlimit(1000000)

n = int(eval(input()))
a = [int(i) for i in 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 = {}
dp = [ float('inf')  for i in range(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
#!/usr/bin/python3

import sys
from bisect import bisect_left

sys.setrecursionlimit(1000000)

n = int(eval(input()))
a = [int(i) for i in 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 for i in range(n) ]
dp = [ float('inf')  for i in range(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 = [int(i) for i in 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 for i in range(n) ]
dp = [ float('inf')  for i in range(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
#!/usr/bin/python3

import sys
from bisect import bisect_left

sys.setrecursionlimit(1000000)

n = int(eval(input()))
a = [int(i) for i in 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 = [int(i) for i in 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
#!/usr/bin/python3

import sys
from bisect import bisect_left

sys.setrecursionlimit(1000000)

n = int(eval(input()))
a = [int(i) for i in 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

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

        if a[ch] > dp[-1]:
            dp.append(a[ch])
            mlen[ch] = len(dp)
            getmlen(ch, cur)
            dp.pop(-1)
        else:
            idx = bisect_left(dp, a[ch])
            ov = dp[idx]
            dp[idx] = a[ch]
            mlen[ch] = len(dp)
            getmlen(ch, cur)
            dp[idx] = ov
            

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

for i in range(n):
    print((mlen[i]))
# Original solution
from bisect import bisect_left
import sys
sys.setrecursionlimit(10 ** 7)

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

edges = [[] for _ in range(N)]
for _ in range(N - 1):
    fr, to = map(lambda a: int(a) - 1, input().split())
    edges[fr].append(to)
    edges[to].append(fr)

ans = [0] * N
L = [-10**18]

def search(now, pr):
    a = A[now]
    i = bisect_left(L, a)
    isAppended = False
    prevValue = -1

    if i == len(L):
        L.append(a)
        isAppended = True
    else:
        prevValue = L[i]
        if L[i] > a:
            L[i] = a

    ans[now] = len(L) - 1

    for to in edges[now]:
        if to == pr:
            continue
        search(to, now)

    if isAppended:
        L.pop()
    else:
        L[i] = prevValue

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


# Optimized solution
from bisect import bisect_left

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

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

order = []
parent = [-1] * (N + 1)
st = [1]
while st:
    now = st.pop()
    order.append(now)
    if now > 0:
        st.append(-now)
        for to in edges[now]:
            if to == parent[now]:
                continue
            st.append(to)
            parent[to] = now

L = [-10**18]
ans = [-1] * (N + 1)
st = [(-1, -1)] * (N + 1)

for now in order:
    if now < 0:
        val, idx = st[-now]
        if val == -1:
            L.pop()
        if val > 0:
            L[idx] = val
        continue

    a = A[now - 1]
    i = bisect_left(L, a)

    if len(L) == i:
        L.append(a)
    else:
        st[now] = (L[i], i)
        if L[i] > a:
            L[i] = a

    ans[now] = len(L) - 1

print(*ans[1:], sep='\n')
# Original solution
from bisect import bisect_left

N=int(input())
*A,=map(int,input().split())
G=[[] for _ in range(N)]
ab = [tuple(map(int,input().split())) for _ in range(N-1)]
for a,b in ab:
  G[a-1].append(b-1)
  G[b-1].append(a-1)
  
def bfs():
    from collections import deque
    dp = [[] for _ in range(N)]
    dp[0] = [A[0]]
    seen = [0]*N
    todo = deque()
    seen[0]=1
    todo.append(0)
    while todo:
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          idx = bisect_left(dp[a],A[b])
          if idx == len(dp[a]): dp[b] = dp[a]+[A[b]]
          else: dp[b] = [dp[a][i] if i != idx else A[b] for i in range(len(dp[a]))]
          seen[b] = 1
          todo.append(b)
    return dp
  
dp = bfs()
  
print(*[len(dp[i]) for i in range(N)],sep="\n")


# Optimized solution
from bisect import bisect_left

N=int(input())
*A,=map(int,input().split())
INF=10**20
G=[[] for _ in range(N)]
ab = [tuple(map(int,input().split())) for _ in range(N-1)]
for a,b in ab:
  G[a-1].append(b-1)
  G[b-1].append(a-1)
  
def dfs(a0):
    seen =[0]*len(G)
    todo = [~a0, a0]
    while todo:
        a = todo.pop()
        if a >= 0:
            seen[a] = 1
            idx = bisect_left(lis,A[a])
            his[a] = (idx,lis[idx])
            lis[idx] = A[a]
            dp[a] = bisect_left(lis,INF)
            for b in G[a]:
                if seen[b]: continue
                todo.append(~b)
                todo.append(b)
        else:
          idx,val = his[~a]
          lis[idx] = val
    return
  
lis = [INF]*N
dp = [0]*N
his = {}
dfs(0)
print(*dp,sep="\n")
# Original solution
from bisect import bisect_left
import sys
sys.setrecursionlimit(10**7)
# input = sys.stdin.readline

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

INF = 999999999999999999999999

n = int(input())
A = [-INF] + get_nums_l()

log(n)
log(A)

edges = [ [] for _ in range(n+1) ]
for _ in range(n-1):
#for line in map(lambda s: s.strip(), sys.stdin.readlines()):
    line = input()
    log(line)
    u,v = map(int, line.split())
    edges[u].append(v)
    edges[v].append(u)

def dfs(dp, u, p=None):

    # log(u)
    # log(dp)

    # dpの中でA[u]以上の値が入っている最小のindex
    i = bisect_left(dp, A[u])

    old = dp[i]
    dp[i] = A[u]

    # 有効値(INF以外)が入っている最大のindex
    ans[u] = bisect_left(dp, INF) - 1

    for v in edges[u]:
        if v == p:
            continue
        dfs(dp, v, u)

    # 巻き戻し
    dp[i] = old

# ans[i] = ノード1からノードiへの経路中の最長増加部分列長
ans = [0] * (n+1)

# dp[i] = 最長増加部分列長がiの場合の末尾ノード値の最小
# dp[0]は使用しないので負の無限大を入れておく
dp = [INF] * (n+1)
dp[0] = -INF

dfs(dp, 1, None)

for i in range(1, n+1):
    print(ans[i])


# Optimized solution
from bisect import bisect_left
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

INF = 999999999999999999999999

n = int(input())
A = [-INF] + get_nums_l()

log(n)
log(A)

edges = [ [] for _ in range(n+1) ]
for _ in range(n-1):
#for line in map(lambda s: s.strip(), sys.stdin.readlines()):
    line = input().strip()
    log(line)
    u,v = map(int, line.split())
    edges[u].append(v)
    edges[v].append(u)

def dfs(dp, u, p=None):

    # log(u)
    # log(dp)

    # dpの中でA[u]以上の値が入っている最小のindex
    i = bisect_left(dp, A[u])

    old = dp[i]
    dp[i] = A[u]

    # 有効値(INF以外)が入っている最大のindex
    ans[u] = bisect_left(dp, INF) - 1

    for v in edges[u]:
        if v == p:
            continue
        dfs(dp, v, u)

    # 巻き戻し
    dp[i] = old

# ans[i] = ノード1からノードiへの経路中の最長増加部分列長
ans = [0] * (n+1)

# dp[i] = 最長増加部分列長がiの場合の末尾ノード値の最小
# dp[0]は使用しないので負の無限大を入れておく
dp = [INF] * (n+1)
dp[0] = -INF

dfs(dp, 1, None)

for i in range(1, n+1):
    print(ans[i])
# Original solution
from bisect import bisect_left
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

INF = 999999999999999999999999

n = int(input())
A = [-INF] + get_nums_l()

log(n)
log(A)

edges = [ [] for _ in range(n+1) ]
for _ in range(n-1):
#for line in map(lambda s: s.strip(), sys.stdin.readlines()):
    line = input().strip()
    log(line)
    u,v = map(int, line.split())
    edges[u].append(v)
    edges[v].append(u)

def dfs(dp, u, p=None):

    # log(u)
    # log(dp)

    # dpの中でA[u]以上の値が入っている最小のindex
    i = bisect_left(dp, A[u])

    old = dp[i]
    dp[i] = A[u]

    # 有効値(INF以外)が入っている最大のindex
    ans[u] = bisect_left(dp, INF) - 1

    for v in edges[u]:
        if v == p:
            continue
        dfs(dp, v, u)

    # 巻き戻し
    dp[i] = old

# ans[i] = ノード1からノードiへの経路中の最長増加部分列長
ans = [0] * (n+1)

# dp[i] = 最長増加部分列長がiの場合の末尾ノード値の最小
# dp[0]は使用しないので負の無限大を入れておく
dp = [INF] * (n+1)
dp[0] = -INF

dfs(dp, 1, None)

for i in range(1, n+1):
    print(ans[i])


# Optimized solution
from bisect import bisect_left
import sys
sys.setrecursionlimit(10**7)

def input(): return sys.stdin.readline().strip()

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

INF = 999999999999999999999999

n = int(input())
A = [-INF] + get_nums_l()

# log(n)
# log(A)

edges = [ [] for _ in range(n+1) ]
for _ in range(n-1):
#for line in map(lambda s: s.strip(), sys.stdin.readlines()):
    line = input().strip()
    # log(line)
    u,v = map(int, line.split())
    edges[u].append(v)
    edges[v].append(u)

def dfs(dp, u, p=None):

    # log(u)
    # log(dp)

    # dpの中でA[u]以上の値が入っている最小のindex
    i = bisect_left(dp, A[u])

    old = dp[i]
    dp[i] = A[u]

    # 有効値(INF以外)が入っている最大のindex
    ans[u] = bisect_left(dp, INF) - 1

    for v in edges[u]:
        if v == p:
            continue
        dfs(dp, v, u)

    # 巻き戻し
    dp[i] = old

# ans[i] = ノード1からノードiへの経路中の最長増加部分列長
ans = [0] * (n+1)

# dp[i] = 最長増加部分列長がiの場合の末尾ノード値の最小
# dp[0]は使用しないので負の無限大を入れておく
dp = [INF] * (n+1)
dp[0] = -INF

dfs(dp, 1, None)

for i in range(1, n+1):
    print(ans[i])
# Original solution
from bisect import bisect_left
import sys
sys.setrecursionlimit(10**7)

# def input(): return sys.stdin.readline().strip()

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

INF = 999999999999999999999999

n = int(input())
A = [-INF] + get_nums_l()

# log(n)
# log(A)

edges = [ [] for _ in range(n+1) ]
for _ in range(n-1):
#for line in map(lambda s: s.strip(), sys.stdin.readlines()):
    line = input().strip()
    # log(line)
    u,v = map(int, line.split())
    edges[u].append(v)
    edges[v].append(u)

def dfs(dp, u, p=None):

    # log(u)
    # log(dp)

    # dpの中でA[u]以上の値が入っている最小のindex
    i = bisect_left(dp, A[u])

    old = dp[i]
    dp[i] = A[u]

    # 有効値(INF以外)が入っている最大のindex
    ans[u] = bisect_left(dp, INF) - 1

    for v in edges[u]:
        if v == p:
            continue
        dfs(dp, v, u)

    # 巻き戻し
    dp[i] = old

# ans[i] = ノード1からノードiへの経路中の最長増加部分列長
ans = [0] * (n+1)

# dp[i] = 最長増加部分列長がiの場合の末尾ノード値の最小
# dp[0]は使用しないので負の無限大を入れておく
dp = [INF] * (n+1)
dp[0] = -INF

dfs(dp, 1, None)

for i in range(1, n+1):
    print(ans[i])


# Optimized solution
from bisect import bisect_left
import sys
sys.setrecursionlimit(10**7)

def input(): return sys.stdin.readline().strip()

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

INF = 999999999999999999999999

n = int(input())
A = [-INF] + get_nums_l()

# log(n)
# log(A)

edges = [ [] for _ in range(n+1) ]
for _ in range(n-1):
# for line in map(lambda s: s.strip(), sys.stdin.readlines()):
    line = input()
    # log(line)
    u,v = map(int, line.split())
    edges[u].append(v)
    edges[v].append(u)

def dfs(dp, u, p=None):

    # log(u)
    # log(dp)

    # dpの中でA[u]以上の値が入っている最小のindex
    i = bisect_left(dp, A[u])

    old = dp[i]
    dp[i] = A[u]

    # 有効値(INF以外)が入っている最大のindex
    ans[u] = bisect_left(dp, INF) - 1

    for v in edges[u]:
        if v == p:
            continue
        dfs(dp, v, u)

    # 巻き戻し
    dp[i] = old

# ans[i] = ノード1からノードiへの経路中の最長増加部分列長
ans = [0] * (n+1)

# dp[i] = 最長増加部分列長がiの場合の末尾ノード値の最小
# dp[0]は使用しないので負の無限大を入れておく
dp = [INF] * (n+1)
dp[0] = -INF

dfs(dp, 1, None)

for i in range(1, n+1):
    print(ans[i])
# Original solution
import bisect
import sys
sys.setrecursionlimit(1000000)

input = sys.stdin.readline

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

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

ans = [0] * n
visited = [0] * n
visited[0] = 1


def dfs(i, l):
    s = a[i]
    if len(l) == 0 or s > l[-1]:
        l.append(s)
    else:
        l[bisect.bisect_left(l, s)] = s
    ans[i] = len(l)

    for ni in tree[i]:
        if not visited[ni]:
            visited[ni] = 1
            dfs(ni, l[:])


dfs(0, [])

for i in ans:
    print(i)


# Optimized solution
import bisect
import sys
sys.setrecursionlimit(1000000)

input = sys.stdin.readline

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

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

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

def dfs(i):
    s = a[i]
    pi = -1
    pv = -1
    if len(l) == 0 or s > l[-1]:
        l.append(s)
    else:
        pi = bisect.bisect_left(l, s)
        pv = l[pi]
        l[pi] = s
    ans[i] = len(l)

    for ni in tree[i]:
        if not visited[ni]:
            visited[ni] = 1
            dfs(ni)
            
    if pi == -1:
        l.pop()
    else:
        l[pi] = pv


dfs(0)

for i in ans:
    print(i)
# Original solution
from collections import deque
from bisect import bisect_left, bisect_right
n = int(eval(input()))
a = list(map(int, input().split()))

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

dp = [float('inf') for _i in range(n+1)]
q = [[0, dp]]
q = deque(q)
while q:
    p, d = q.popleft()
    i = bisect_left(d, a[p])
    d[i] = a[p]
    result[p] = bisect_left(d, float("inf")-1)
    for i in tree[p]:
        if result[i] < 0:
            q.appendleft([i, d.copy()])

for i in result:
    print(i)

# Optimized solution
from bisect import bisect_left
n = int(eval(input()))
a = list(map(int, input().split()))

result = [-1 for _ in range(n)]
tree = [[] for _ in range(n)]
for _i in range(n-1):
    u, v = list(map(int, input().split()))
    u, v = u-1, v-1
    tree[u].append(v)
    tree[v].append(u)
INF = float('inf')
dp = [INF for _i in range(n+1)]


def dfs(p, d, x):
    i = bisect_left(d, a[p])
    d[i] = a[p]
    result[p] = bisect_left(d, INF)
    for j in tree[p]:
        if j != x:
            dfs(j, d.copy(), p)

dfs(0, dp, -1)

for i in result:
    print(i)
# Original solution
n = int(eval(input()))
a = list(map(int, input().split()))
uv = [list(map(int, input().split())) for _ in range(n - 1)]

import sys
sys.setrecursionlimit(10 ** 7)

from collections import defaultdict
g = defaultdict(list)
for i in range(n - 1):
    u = uv[i][0] - 1
    v = uv[i][1] - 1
    g[u].append(v)
    g[v].append(u)

from bisect import bisect_left
ans = [0] * n
visited = [0] * n

def dfs(cur, dp):
    visited[cur] = 1
    idx = bisect_left(dp, a[cur])
    #print(cur, dp, idx)

    dp_new = dp.copy()
    if idx == len(dp_new):
        dp_new.append(a[cur])
    else:
        dp_new[idx] = a[cur]

    ans[cur] = len(dp_new)

    for target in g[cur]:
        if visited[target] == 0:
            dfs(target, dp_new)

dfs(0, [])

for _ans in ans:
    print(_ans)


# Optimized solution
n = int(eval(input()))
a = list(map(int, input().split()))
uv = [list(map(int, input().split())) for _ in range(n - 1)]

from collections import defaultdict
g = defaultdict(list)
for i in range(n - 1):
    u = uv[i][0] - 1
    v = uv[i][1] - 1
    g[u].append(v)
    g[v].append(u)

from bisect import bisect_left
ans = [0] * n
visited = [0] * n

from collections import deque
q = deque([(0, [])])
visited[0] = 1

while q:
    cur, dp = q.popleft()

    idx = bisect_left(dp, a[cur])
    dp_new = dp.copy()
    if idx == len(dp_new):
        dp_new.append(a[cur])
    else:
        dp_new[idx] = a[cur]

    ans[cur] = len(dp_new)

    for target in g[cur]:
        if visited[target] == 0:
            visited[target] = 1
            q.append((target, dp_new))


for _ans in ans:
    print(_ans)
# Original solution
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return eval(input())
     
def main():
    N = I()
    A = LI()
    G = [[] for _ in range(N)]
    dp = [inf for _ in range(N)]
    ans = [0] * N
    for i in range(N-1):
        a, b = LI_()
        G[a].append(b)
        G[b].append(a)

    def update_dp(i):
        j = bisect.bisect_left(dp, A[i])
        before_val = dp[j]
        dp[j] = A[i]
        return j, before_val
    visited = set()
    def dfs(v):
        visited.add(v)
        changed_i, before_val = update_dp(v)
        ans[v] = bisect.bisect_left(dp, inf)
        for next_v in G[v]:
            if next_v in visited:
                continue
            dfs(next_v)

        # restore dp
        dp[changed_i] = before_val

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

main()



# Optimized solution
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return eval(input())
     
def main():
    N = I()
    A = LI()
    G = [[] for _ in range(N)]
    dp = [inf for _ in range(N)]
    ans = [0] * N
    for i in range(N-1):
        a, b = LI_()
        G[a].append(b)
        G[b].append(a)

    def update_dp(i):
        j = bisect.bisect_left(dp, A[i])
        before_val = dp[j]
        dp[j] = A[i]
        return j, before_val

    visited = set()

    def dfs(v):
        visited.add(v)

        j = bisect.bisect_left(dp, A[v])
        before_val = dp[j]
        dp[j] = A[v]

        ans[v] = bisect.bisect_left(dp, inf)
        for next_v in G[v]:
            if next_v in visited:
                continue
            dfs(next_v)

        # restore dp
        dp[j] = before_val

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

main()
# Original solution
import sys
from copy import copy
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

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

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

ans = [0] * n


def dfs(v, v_p, dp):
    # print(v, v_p, dp)
    ans[v] = len(dp)
    for v_next in graph[v]:
        if v_next == v_p:
            continue

        # print(dp)
        dp2 = copy(dp)
        if a[v_next] > dp2[-1]:
            dp2.append(a[v_next])
            dfs(v_next, v, dp2)
            dp2 = dp2[:len(dp2) - 1]
        else:
            idx = bisect_left(dp2, a[v_next])
            past = dp2[idx]
            dp2[idx] = a[v_next]
            dfs(v_next, v, dp2)
            dp2[idx] = past


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


# Optimized solution
import sys
from copy import copy
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

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

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

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


def dfs(v, v_p, dp_len):
    # print(v, v_p, dp)
    ans[v] = dp_len
    for v_next in graph[v]:
        if v_next == v_p:
            continue

        # print(dp)
        if a[v_next] > dp[dp_len - 1]:
            past = dp[dp_len]
            dp[dp_len] = a[v_next]
            dfs(v_next, v, dp_len + 1)
            dp[dp_len] = past
        else:
            idx = bisect_left(dp, a[v_next])
            # always idx < dp_len
            past = dp[idx]
            dp[idx] = a[v_next]
            dfs(v_next, v, dp_len)
            dp[idx] = past


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