CodeEff/ECCO huggingface dataset:
# Original solution
def main():
    from bisect import bisect_left
    from collections import deque
    import sys
    input = sys.stdin.readline

    inf = 1 << 30

    N = int(input())
    *a, = map(int, input().split())

    g = tuple(set() for _ in range(N))
    for _ in range(N - 1):
        u, v = (int(x) - 1 for x in input().split())
        g[u].add(v)
        g[v].add(u)

    ans = [0] * N
    lis = [None for _ in range(N)]
    lis[0] = [inf] * N

    dq = deque([0])

    while dq:
        v = dq.popleft()

        if ans[v]: continue

        i = bisect_left(lis[v], a[v])
        lis[v][i] = a[v]
        ans[v] = bisect_left(lis[v], inf)

        for u in g[v]:
            if ans[u]: continue
            dq.append(u)
            lis[u] = lis[v].copy()

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


if __name__ == '__main__':
    main()

# dp[i]=長さiの増加部分列の末尾としてありえる最小値
# というテーブルを持っておいて、数列を列を前から見ながら二分探索で更新箇所を探す


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

    inf = 1 << 30

    N = int(input())
    *a, = map(int, input().split())

    g = tuple(set() for _ in range(N))
    for _ in range(N - 1):
        u, v = (int(x) - 1 for x in input().split())
        g[u].add(v)
        g[v].add(u)

    ans = [0] * N
    lis = [inf] * N
    lis[0] = a[0]

    def dfs(v, p=-1):
        ans[v] = bisect_left(lis, inf)
        for u in g[v]:
            if p == u: continue
            i = bisect_left(lis, a[u])
            prev_at_i = lis[i]
            lis[i] = a[u]
            dfs(u, v)
            lis[i] = prev_at_i

    dfs(0)

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


if __name__ == '__main__':
    main()

# dp[i]=長さiの増加部分列の末尾としてありえる最小値
# というテーブルを持っておいて、数列を列を前から見ながら二分探索で更新箇所を探す
# Original solution
n=int(eval(input()))
a=list(map(int,input().split()))
g = [[]for _ in range(n)]
for i in range(n-1):
    u,v=list(map(int,input().split()))
    g[u-1].append(v-1)
    g[v-1].append(u-1)
import copy
import queue
import bisect
check = [False]*n
check[0] = True
li = [a[0]]
q= queue.Queue()
q.put([0,li])
ans = [0]*n
ans[0] = 1
while not q.empty():
    now,lisOrigin= q.get()
    for ne in g[now]:
        if check[ne]:
            continue
        check[ne] = True
        lis = copy.deepcopy(lisOrigin)
        if a[ne] > lis[-1]:
            lis.append(a[ne])
        else:
            lis[bisect.bisect_left(lis,a[ne])] = a[ne]
        q.put([ne,lis])
        ans[ne] = len(lis)

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

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

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

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

def dfs(now, pre):
    idx = bisect_left(lis, a[now])
    tmp = lis[idx]
    lis[idx] = a[now]
    ans[now] = bisect_left(lis, float('inf'))
    for to in g[now]:
        if to == pre:
            continue
        dfs(to, now)
    lis[idx] = tmp

dfs(0,-1)
for x in ans:
    print(x)
# Original solution
import sys
sys.setrecursionlimit(1000000)


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


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

dp = [10 ** 18] * (n + 10)
dp[0] = 0
ans1 = [0] * n
ans2 = [0] * n


def dfs(i=0, r=-1):
    global dp, ans1, ans2
    mi = 0
    ma = n
    while mi != ma:
        mm = (mi + ma) // 2
        if dp[mm] >= aa[i]:
            ma = mm
        else:
            mi = mm + 1

    be = dp[mi]
    dp[mi] = min(dp[mi], aa[i])
    ans1[i] = mi
    ans2[i] = max(ans1[i], ans2[r])

    for j in e[i]:
        if j == r:
            continue
        dfs(j, i)

    dp[mi] = be


dfs()
for i in ans2:
    print(i)


# Optimized solution
import sys
sys.setrecursionlimit(1000000)


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


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

dp = [10 ** 9] * (n + 10)
dp[0] = 0
ans1 = [0] * n
ans2 = [0] * n


def dfs(i=0, r=-1):
    global dp, ans1, ans2
    mi = 0
    ma = n
    while mi != ma:
        mm = (mi + ma) // 2
        if dp[mm] >= aa[i]:
            ma = mm
        else:
            mi = mm + 1

    be = dp[mi]
    dp[mi] = min(dp[mi], aa[i])
    ans1[i] = mi
    ans2[i] = max(ans1[i], ans2[r])

    for j in e[i]:
        if j == r:
            continue
        dfs(j, i)

    dp[mi] = be


dfs()
print(("\n".join(map(str, ans2))))
# Original solution
from bisect import bisect_left as bl
import sys
sys.setrecursionlimit(10**6)
n=int(eval(input()))
a=list(map(int,input().split()))
t=[[]for i in range(n)]
for i in range(n-1):
    u,v=list(map(int,input().split()))
    t[u-1].append(v-1)
    t[v-1].append(u-1)
b=[0]*n
dp=[float("inf")]*n
def f(c,d,dp):
    h=bl(dp,a[c])
    q=dp[::]
    q[h]=a[c]
    b[c]=bl(q,float("INF"))
    for i in t[c]:
        if i!=d:f(i,c,q)
f(0,-1,dp)
for i in b:
    print(i)

# Optimized solution
from bisect import bisect_left as bl
import sys
sys.setrecursionlimit(10**6)
n=int(eval(input()))
a=list(map(int,input().split()))
t=[[]for i in range(n)]
for i in range(n-1):
    u,v=list(map(int,input().split()))
    t[u-1].append(v-1)
    t[v-1].append(u-1)
b=[0]*n
dp=[float("inf")]*n
def f(c,d):
    h=bl(dp,a[c])
    g=dp[h]
    dp[h]=min(dp[h],a[c])
    b[c]=bl(dp,float("INF"))
    for i in t[c]:
        if i!=d:f(i,c)
    dp[h]=g
f(0,-1)
for i in b:
    print(i)
# Original solution
import sys
sys.setrecursionlimit(10**8)
from bisect import bisect_left, bisect_right
from copy import copy, deepcopy
N = int(input())
A = list(map(int, input().split()))
edge = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

def dfs(v,LIS):
    if len(edge[v])==0:
        return
    for u in edge[v]:
        if visited[u]==False:
            visited[u]=True
            lis = copy(LIS)
            if A[u] > lis[-1]:
                lis.append(A[u])
            else:
                ind = bisect_left(LIS,A[u])
                lis[ind] = A[u]
            ans[u] = len(lis)
            dfs(u,lis)
    return

ans = [0]*N
visited = [False]*N
visited[0]=True
LIS = [A[0]]
ans[0] = 1
dfs(0,LIS)
print(*ans, sep='\n')


# Optimized solution
import sys
sys.setrecursionlimit(10**8)
from bisect import bisect_left, bisect_right
N = int(input())
A = list(map(int, input().split()))
edge = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

def dfs(v,LIS):
    if len(edge[v])==0:
        return
    for u in edge[v]:
        if visited[u]==False:
            visited[u]=True
            if A[u] > LIS[-1]:
                LIS.append(A[u])
                ans[u] = len(LIS)
                dfs(u,LIS)
                LIS.pop()
            else:
                ind = bisect_left(LIS,A[u])
                stack = LIS[ind]
                LIS[ind] = A[u]
                ans[u] = len(LIS)
                dfs(u,LIS)
                LIS[ind] = stack
    return

ans = [0]*N
visited = [False]*N
visited[0]=True
LIS = [A[0]]
ans[0] = 1
dfs(0,LIS)
print(*ans, sep='\n')
# Original solution
import sys
sys.setrecursionlimit(10**7)

import sys
input = sys.stdin.readline

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

from collections import defaultdict
G = defaultdict(list)

for _ in range(n-1):
    u,v = list(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 i in range(n):
        if dp[i] == "inf":
            ansl[pos] = i
            break
    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]))




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

import sys
input = sys.stdin.readline

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

from collections import defaultdict
G = defaultdict(list)

for _ in range(n-1):
    u,v = list(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]))
# Original solution
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    a=list(map(int,input().split()))
    edge=[[] for _ in range(N)]
    for _ in range(N-1):
        x,y=map(int1,input().split())
        edge[x].append(y)
        edge[y].append(x)
    stack=[(0,1)]
    used=[False]*N
    ans=[0]*N
    dpdp=[[0]+[INF]*(N+10)]
    prev_l=1
    while stack:
        v,l=stack.pop()
        used[v]=True
        for _ in range(prev_l-l):
            dpdp.pop()
        prev_l=l
        dp=dpdp[-1][:]
        dp[bisect_right(dp,a[v]-1,hi=l)]=a[v]
        ans[v]=bisect_left(dp,INF,hi=l+1)-1
        f=True
        for nv in edge[v]:
            if not used[nv]:
                if f:
                    dpdp.append(dp)
                    f=False
                stack.append((nv,l+1))
    for a in ans:
        print(a)

if __name__ == '__main__':
    main()


# Optimized solution
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    a=list(map(int,input().split()))
    edge=[[] for _ in range(N)]
    for _ in range(N-1):
        x,y=map(int1,input().split())
        edge[x].append(y)
        edge[y].append(x)
    stack=[(0,1)]
    used=[False]*N
    ans=[0]*N
    dp=[INF]*(N+1)
    dp[0]=0
    dpdp=[]
    prev_l=1
    def dfs(v,l):
        used[v]=True
        index=bisect_right(dp,a[v]-1,hi=l)
        dpdp=(index,dp[index])
        dp[index]=a[v]
        ans[v]=bisect_left(dp,INF,hi=l+1)-1
        for nv in edge[v]:
            if not used[nv]:
                i,x=dfs(nv,l+1)
                dp[i]=x
        return dpdp
    dfs(0,1)
    for a in ans:
        print(a)

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


def main():
    N = int(eval(input()))
    A = list(map(int, input().split()))
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        u, v = list(map(int, input().split()))
        u -= 1
        v -= 1
        edge[u].append(v)
        edge[v].append(u)
    dp = [[] for _ in range(N)]
    B = [[] for _ in range(N)]
    dist = [-1]*N
    dist[0] = 0
    dp[0] = [A[0]]
    B[0] = [A[0]]
    queue = deque([0])
    while queue:
        now = queue.popleft()
        d = dist[now]
        for i in edge[now]:
            if dist[i] > -1:
                continue
            dist[i] = d + 1
            queue.append(i)
            dp[i] += dp[now]
            if A[i] > dp[i][-1]:
                dp[i].append(A[i])
            else:
                dp[i][bisect.bisect_left(dp[i], A[i])] = A[i]

    for i in range(N):
        print((len(dp[i])))

    
if __name__ == "__main__":
    main()

# Optimized solution
import sys
import bisect
from collections import deque
sys.setrecursionlimit(4100000)
input = sys.stdin.readline


def main():
    N = int(eval(input()))
    A = list(map(int, input().split()))
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        u, v = list(map(int, input().split()))
        u -= 1
        v -= 1
        edge[u].append(v)
        edge[v].append(u)
    LIS = [A[0]]
    dist = [-1]*N
    dist[0] = 0
    ans = [0] * N
    ans[0] = 1
    queue = deque()
    queue.append((0,LIS))
    while queue:
        now, LIS_tmp = queue.popleft()
        d = dist[now]
        for i in edge[now]:
            tmp = LIS_tmp[:]
            if dist[i] > -1:
                continue
            dist[i] = d + 1
            if A[i] > tmp[-1]:
                tmp.append(A[i])
            else:
                tmp[bisect.bisect_left(tmp, A[i])] = A[i]
            queue.append((i,tmp))
            ans[i] = len(tmp)

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

    
if __name__ == "__main__":
    main()
# Original solution
import sys
import bisect
from collections import deque
sys.setrecursionlimit(4100000)
input = sys.stdin.readline


def main():
    N = int(eval(input()))
    A = list(map(int, input().split()))
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        u, v = list(map(int, input().split()))
        u -= 1
        v -= 1
        edge[u].append(v)
        edge[v].append(u)
    LIS = [A[0]]
    dist = [-1]*N
    dist[0] = 0
    ans = [0] * N
    ans[0] = 1
    queue = deque()
    queue_append = queue.append
    queue_append((0,LIS))
    while queue:
        now, LIS_tmp = queue.popleft()
        d = dist[now]
        for i in edge[now]:
            tmp = LIS_tmp[:]
            tmp_append = tmp.append
            A_now = A[i]
            if dist[i] > -1:
                continue
            dist[i] = d + 1
            if A_now > tmp[-1]:
                tmp_append(A_now)
            else:
                tmp[bisect.bisect_left(tmp, A_now)] = A_now
            queue_append((i,tmp))
            ans[i] = len(tmp)

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

    
if __name__ == "__main__":
    main()

# Optimized solution
import sys
import bisect
from collections import deque
sys.setrecursionlimit(4100000)
input = sys.stdin.readline

def main():
    N = int(eval(input()))
    A = list(map(int, input().split()))
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        u, v = list(map(int, input().split()))
        u -= 1
        v -= 1
        edge[u].append(v)
        edge[v].append(u)

    ans = [0] * (N + 1)
    LIS = [-1]
    
    def dfs(v, p = N):
        if A[v] > LIS[-1]:
            LIS.append(A[v])
            ans[v] = ans[p] + 1
            for u in edge[v]:
                if u == p:
                    continue
                dfs(u,v)
            LIS.pop()
        else:
            ans[v] = ans[p]
            idx = bisect.bisect_left(LIS, A[v])
            old = LIS[idx]
            LIS[idx] = A[v]
            for u in edge[v]:
                if u == p:
                    continue
                dfs(u,v)
            LIS[idx] = old
    dfs(0)
    for i in range(N):
        print((ans[i]))

if __name__ == "__main__":
    main()
# Original solution
import sys
readline = sys.stdin.readline

sys.setrecursionlimit(10**6)


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

    query = (list(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 ** 9 + 7
    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] = dp.index(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()


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

sys.setrecursionlimit(10**6)


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

    query = (list(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()
# Original solution
from collections import deque
import bisect
from copy import copy

n = int(input())
a = list(map(int, input().split()))
to=[list() for _ in range(n)]

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

d= deque()
INF=10010001001
dpinit = [a[0]]
d.append((0,-1,copy(dpinit)))
ansls=[0]*n
ansls[0]=1
while d:
    u,p,dp = d.popleft()
    for v in to[u]:
        if v==p:
            continue
        idx=bisect.bisect_left(dp,a[v])
        if idx<len(dp):
            prv=dp[idx]
            dp[idx]=a[v]       
        else:
            dp.append(a[v])
            prv=-1
        ansls[v]=len(dp)
        d.append((v,u,copy(dp)))
        if prv!=-1:
            dp[idx]=prv
        else:
            dp.pop()


print(*ansls,sep='\n')


# Optimized solution
from collections import deque
import bisect
import sys
sys.setrecursionlimit(500000)

n = int(input())
a = list(map(int, input().split()))
to=[list() for _ in range(n)]

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

INF=1001001001
dp = [INF]*n
dp[0]=a[0]
ansls=[0]*n
ansls[0]=1
history=deque()
def dfs(u,p,rank):
    for v in to[u]:
        if v==p:
            continue
        idx=bisect.bisect_left(dp,a[v])
        prv=dp[idx]
        dp[idx]=a[v]       
        history.append((idx,prv))
        ansls[v]=bisect.bisect_left(dp,INF)
        dfs(v,u,rank+1)
        while len(history)>rank:
            idx,prv =history.pop()
            dp[idx] = prv

dfs(0,-1,0)

print(*ansls,sep='\n')
# Original solution
from collections import deque
import bisect
import sys
def input(): return sys.stdin.readline().rstrip()
 
def main():
    n = int(input())
    graph = [[] for _ in range(n+1)]
 
    A = [0]+list(map(int, input().split()))
 
    for i in range(n-1):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
 
    dist = [-1] * (n+1)
    dist[0] = 0
    dist[1] = 1
 
    d = deque()
    d.append((1, [0, A[1]]))
 
    while d:
        v, dp = d.popleft()
        for i in graph[v]:
            if dist[i] != -1:
                continue
            if dp[-1] < A[i]:
                dp.append(A[i])
                d.append((i, dp.copy()))
                dist[i] = len(dp)-1
                dp.pop()
            else:
                bis = bisect.bisect_left(dp, A[i])
                updatetask=dp[bis]
                dp[bis] = A[i]
                dist[i] = len(dp)-1
                d.append((i, dp.copy()))
                dp[bis]=updatetask
 
    print(*dist[1:], sep="\n")
 
if __name__ == '__main__':
    main()


# Optimized solution
from collections import deque
import sys
import bisect
def input(): return sys.stdin.readline().rstrip()

n=int(input())
A=[0]+list(map(int, input().split()))

graph = [[] for _ in range(n+1)]

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

visited = [-1] * (n+1)
visited[0] = 0
visited[1] = 1

d = deque()
d.append(1)
dp=[10**10]*(n+1)
dp[0]=0
dp[1]=A[1]
update_task=[() for _ in range(n+1)]
update_task[1]=(1,0)
while d:
    v = d[-1]
    if graph[v] == []:
        d.pop()
        index,atai=update_task[v]
        dp[index]=atai
    else:
        i = graph[v].pop()
        if visited[i] != -1:
            continue
        bis = bisect.bisect_left(dp, A[i])
        update_task[i]=(bis,dp[bis])
        dp[bis] = A[i]
        visited[i] = bisect.bisect_left(dp, 10**10-100)-1
        d.append(i)

print(*visited[1:], sep="\n")
# Original solution
import bisect
import sys


N = int(eval(input()))
a = list(map(int, input().split()))
to = [[] for _ in range(N)]
for _ in range(N - 1):
    u, v = list(map(int, input().split()))
    u -= 1
    v -= 1
    to[u].append(v)
    to[v].append(u)
del u, v

ans = [-1] * N


def dfs(v, dp):
    # dp は参照渡し
    if len(dp) == 0 or a[v] > dp[-1]:
        dp.append(a[v])
        back = -1
    else:
        pos = bisect.bisect_left(dp, a[v])
        back = dp[pos]
        dp[pos] = a[v]
    ans[v] = len(dp)

    for u in to[v]:
        if ans[u] == -1:
            dfs(u, dp)
    if back == -1:
        dp.pop()
    else:
        dp[pos] = back


sys.setrecursionlimit(10 ** 6)
dfs(0, [])


for an in ans:
    print(an)


# Optimized solution
import bisect
import sys


N = int(eval(input()))
a = list(map(int, input().split()))
to = [[] for _ in range(N)]
for _ in range(N - 1):
    u, v = list(map(int, input().split()))
    u -= 1
    v -= 1
    to[u].append(v)
    to[v].append(u)
del u, v


def dfs(v):
    if len(dp) == 0 or a[v] > dp[-1]:
        dp.append(a[v])
        pos = -1
    else:
        pos = bisect.bisect_left(dp, a[v])
        back = dp[pos]
        dp[pos] = a[v]
    ans[v] = len(dp)

    for u in to[v]:
        if ans[u] == -1:
            dfs(u)
    if pos == -1:
        dp.pop()
    else:
        dp[pos] = back


ans = [-1] * N
sys.setrecursionlimit(10 ** 6)
dp = []
dfs(0)


for an in ans:
    print(an)