CodeEff/ECCO huggingface dataset:
# Original solution
import sys
import bisect
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(eval(input()))
    A = [int(x) for x in input().split()]
    UV = [[int(x) for x in input().split()] for _ in range(N - 1)]

    T = [[] for j in range(N + 1)]

    for u, v in UV:
        T[u].append(v)
        T[v].append(u)

    s = collections.deque()

    lis = []
    s.append([1, lis])

    v = set()

    ans = [0] * (N + 1)

    while s:
        c = s[-1]
        ci, clis = c[0], c[1]

        # lis処理
        if ci not in v:
            if len(clis) == 0:
                clis.append(A[ci - 1])
            else:
                if clis[-1] < A[ci - 1]:
                    clis.append(A[ci - 1])
                else:
                    i = bisect.bisect_left(clis, A[ci - 1])
                    clis[i] = A[ci - 1]

            v.add(ci)
            ans[ci] = len(clis)

        if len(T[ci]) >= 1:
            n = T[ci].pop()
            if n in v:
                continue
            s.append([n, clis.copy()])
            continue

        s.pop()

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


if __name__ == '__main__':
    main()


# Optimized solution
import sys
import bisect
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(eval(input()))
    A = [int(x) for x in input().split()]
    UV = [[int(x) for x in input().split()] for _ in range(N - 1)]

    T = [[] for j in range(N + 1)]

    for u, v in UV:
        T[u].append(v)
        T[v].append(u)

    s = collections.deque()

    lis = []
    s.append([1, lis])

    v = set()

    ans = [0] * (N + 1)
    memo = [[] for j in range(N + 1)]

    while s:
        c = s[-1]
        ci, clis = c[0], c[1]

        # lis処理
        if ci not in v:
            if len(clis) == 0:
                clis.append(A[ci - 1])
                memo[ci].append(-1)
            else:
                if clis[-1] < A[ci - 1]:
                    clis.append(A[ci - 1])
                    memo[ci].append(-1)
                else:
                    i = bisect.bisect_left(clis, A[ci - 1])
                    memo[ci].append(i)
                    memo[ci].append(clis[i])
                    clis[i] = A[ci - 1]

            v.add(ci)
            ans[ci] = len(clis)

        if len(T[ci]) >= 1:
            n = T[ci].pop()
            if n in v:
                continue
            s.append([n, clis])
            continue

        if memo[ci][0] == -1:
            if len(clis) >= 1:
                clis.pop()
        else:
            clis[memo[ci][0]] = memo[ci][1]

        s.pop()

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


if __name__ == '__main__':
    main()
# Original solution
import sys
import bisect
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(eval(input()))
    A = [int(x) for x in input().split()]
    UV = [[int(x) for x in input().split()] for _ in range(N - 1)]

    T = [[] for j in range(N + 1)]

    for u, v in UV:
        T[u].append(v)
        T[v].append(u)

    s = collections.deque()

    lis = []
    s.append([1, lis])

    v = set()

    ans = [0] * (N + 1)
    memo = [[] for j in range(N + 1)]

    while s:
        c = s[-1]
        ci, clis = c[0], c[1]

        # lis処理
        if ci not in v:
            if len(clis) == 0:
                clis.append(A[ci - 1])
                memo[ci].append(-1)
            else:
                if clis[-1] < A[ci - 1]:
                    clis.append(A[ci - 1])
                    memo[ci].append(-1)
                else:
                    i = bisect.bisect_left(clis, A[ci - 1])
                    memo[ci].append(i)
                    memo[ci].append(clis[i])
                    clis[i] = A[ci - 1]

            v.add(ci)
            ans[ci] = len(clis)

        if len(T[ci]) >= 1:
            n = T[ci].pop()
            if n in v:
                continue
            s.append([n, clis])
            continue

        if memo[ci][0] == -1:
            if len(clis) >= 1:
                clis.pop()
        else:
            clis[memo[ci][0]] = memo[ci][1]

        s.pop()

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


if __name__ == '__main__':
    main()


# Optimized solution
import sys
import bisect
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(eval(input()))
    A = [int(x) for x in input().split()]
    UV = [[int(x) for x in input().split()] for _ in range(N - 1)]

    T = [[] for j in range(N + 1)]

    for u, v in UV:
        T[u].append(v)
        T[v].append(u)

    s = collections.deque()

    lis = []
    s.append([1, lis])

    v = set()

    ans = [0] * (N + 1)
    memo = [[] for j in range(N + 1)]

    while s:
        c = s[-1]
        ci = c[0]

        # lis処理
        if ci not in v:
            if len(lis) == 0:
                lis.append(A[ci - 1])
                memo[ci].append(-1)
            else:
                if lis[-1] < A[ci - 1]:
                    lis.append(A[ci - 1])
                    memo[ci].append(-1)
                else:
                    i = bisect.bisect_left(lis, A[ci - 1])
                    memo[ci].append(i)
                    memo[ci].append(lis[i])
                    lis[i] = A[ci - 1]

            v.add(ci)
            ans[ci] = len(lis)

        if len(T[ci]) >= 1:
            n = T[ci].pop()
            if n in v:
                continue
            s.append([n, lis])
            continue

        if memo[ci][0] == -1:
            if len(lis) >= 1:
                lis.pop()
        else:
            lis[memo[ci][0]] = memo[ci][1]

        s.pop()

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


if __name__ == '__main__':
    main()
# Original solution
import sys
import bisect
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(eval(input()))
    A = [int(x) for x in input().split()]
    UV = [[int(x) for x in input().split()] for _ in range(N - 1)]

    T = [[] for j in range(N + 1)]

    for u, v in UV:
        T[u].append(v)
        T[v].append(u)

    s = collections.deque()

    lis = []
    s.append([1, lis])

    v = set()

    ans = [0] * (N + 1)
    memo = [[] for j in range(N + 1)]

    while s:
        c = s[-1]
        ci = c[0]

        # lis処理
        if ci not in v:
            if len(lis) == 0:
                lis.append(A[ci - 1])
                memo[ci].append(-1)
            else:
                if lis[-1] < A[ci - 1]:
                    lis.append(A[ci - 1])
                    memo[ci].append(-1)
                else:
                    i = bisect.bisect_left(lis, A[ci - 1])
                    memo[ci].append(i)
                    memo[ci].append(lis[i])
                    lis[i] = A[ci - 1]

            v.add(ci)
            ans[ci] = len(lis)

        if len(T[ci]) >= 1:
            n = T[ci].pop()
            if n in v:
                continue
            s.append([n, lis])
            continue

        if memo[ci][0] == -1:
            if len(lis) >= 1:
                lis.pop()
        else:
            lis[memo[ci][0]] = memo[ci][1]

        s.pop()

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


if __name__ == '__main__':
    main()


# Optimized solution
import sys
import bisect
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(eval(input()))
    A = [int(x) for x in input().split()]
    UV = [[int(x) for x in input().split()] for _ in range(N - 1)]

    T = [[] for j in range(N + 1)]

    for u, v in UV:
        T[u].append(v)
        T[v].append(u)

    s = collections.deque()

    lis = []
    s.append([1, lis])

    ans = [0] * (N + 1)
    memo = [[] for j in range(N + 1)]

    while s:
        c = s[-1]
        ci = c[0]

        # lis処理
        if ans[ci] == 0:
            if len(lis) == 0:
                lis.append(A[ci - 1])
                memo[ci].append(-1)
            else:
                if lis[-1] < A[ci - 1]:
                    lis.append(A[ci - 1])
                    memo[ci].append(-1)
                else:
                    i = bisect.bisect_left(lis, A[ci - 1])
                    memo[ci].append(i)
                    memo[ci].append(lis[i])
                    lis[i] = A[ci - 1]

            ans[ci] = len(lis)

        if len(T[ci]) >= 1:
            n = T[ci].pop()
            if ans[n] != 0:
                continue
            s.append([n, lis])
            continue

        if memo[ci][0] == -1:
            if len(lis) >= 1:
                lis.pop()
        else:
            lis[memo[ci][0]] = memo[ci][1]

        s.pop()

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


if __name__ == '__main__':
    main()
# Original solution
import sys
from bisect import bisect_left, bisect_right
sys.setrecursionlimit(10**6)
def input(): return sys.stdin.readline().strip()


def main():
    N = int(eval(input()))
    A = list(map(int, input().split()))
    repn = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v = list(map(int, input().split()))
        repn[u - 1].append(v - 1)
        repn[v - 1].append(u - 1)
    
    length = [0] * (N + 1)
    dp = [-1]

    """
    やはり各頂点でLIS配列を取ると配列コピーの時間がかかってTLEするので、
    配列は唯一つを扱って、DFSからバックするときに配列も元に戻す操作を行いたい
    （ここの実装の仕方がわからなかった）

    これはdfsを再帰で書いた後に復元操作を追記すれば異常に楽に書ける。。。
    """

    def dfs(v, p=N):
        if A[v] > dp[-1]:
            dp.append(A[v])
            length[v] = length[p] + 1
            for u in repn[v]:
                if u == p: continue
                dfs(u, v)
            dp.pop()
        else:
            length[v] = length[p]
            idx = bisect_left(dp[:length[p]], A[v]) # bisect_rightだとdpに重複する値を書き込んでしまうのでダメ
            old = dp[idx]
            dp[idx] = A[v]
            for u in repn[v]:
                if u == p: continue
                dfs(u, v)
            dp[idx] = old
        #print("v={}, len={}, dp={}".format(v, length[v], dp))

    dfs(0)
    length.pop()
    for ans in length:
        print(ans)
    


if __name__ == "__main__":
    main()


# Optimized solution
import sys
from bisect import bisect_left, bisect_right
sys.setrecursionlimit(2*10**5)
def input(): return sys.stdin.readline().strip()


def main():
    N = int(eval(input()))
    A = list(map(int, input().split()))
    repn = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v = list(map(int, input().split()))
        repn[u - 1].append(v - 1)
        repn[v - 1].append(u - 1)
    
    length = [0] * (N + 1)
    dp = [-1]

    """
    やはり各頂点でLIS配列を取ると配列コピーの時間がかかってTLEするので、
    配列は唯一つを扱って、DFSからバックするときに配列も元に戻す操作を行いたい
    （ここの実装の仕方がわからなかった）

    これはdfsを再帰で書いた後に復元操作を追記すれば異常に楽に書ける。。。
    """

    def dfs(v, p=N):
        if A[v] > dp[-1]:
            dp.append(A[v])
            length[v] = length[p] + 1
            for u in repn[v]:
                if u == p: continue
                dfs(u, v)
            dp.pop()
        else:
            length[v] = length[p]
            idx = bisect_left(dp, A[v]) # bisect_rightだとdpに重複する値を書き込んでしまうのでダメ
            old = dp[idx]
            dp[idx] = A[v]
            for u in repn[v]:
                if u == p: continue
                dfs(u, v)
            dp[idx] = old
        #print("v={}, len={}, dp={}".format(v, length[v], dp))

    dfs(0)
    length.pop()
    for ans in length:
        print(ans)
    


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

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
a = na()
g = []
for i in range(n):
    g.append([])
for i in range(n-1):
    x, y = na()
    g[x-1].append(y-1)
    g[y-1].append(x-1)

sys.setrecursionlimit(300000)
import bisect
def dfs(cur, pre, g, lis, la, anss, a):
    ind = bisect.bisect_left(la, a[cur])
    old = la[ind]
    la[ind] = a[cur]
    nlis = lis + 1 if ind == lis + 1 else lis
    anss[cur] = nlis

    for e in g[cur]:
        if e == pre: continue
        dfs(e, cur, g, nlis, la, anss, a)

    la[ind] = old

anss = [0] * n
la = [999999999999] * (n+1)
la[0] = 0
dfs(0, -1, g, 0, la, anss, a)
for v in anss:
    print(v)

# Optimized solution
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
a = na()
g = []
for i in range(n):
    g.append([])
for i in range(n-1):
    x, y = na()
    g[x-1].append(y-1)
    g[y-1].append(x-1)

sys.setrecursionlimit(230000)
import bisect
def dfs(cur, pre, g, lis, la, anss, a):
    ind = bisect.bisect_left(la, a[cur], 0, lis+1)
    old = la[ind]
    la[ind] = a[cur]
    nlis = lis + 1 if ind == lis + 1 else lis
    anss[cur] = nlis

    for e in g[cur]:
        if e == pre: continue
        dfs(e, cur, g, nlis, la, anss, a)

    la[ind] = old

anss = [0] * n
la = [999999999999] * (n+2)
la[0] = 0
dfs(0, -1, g, 0, la, anss, a)
for v in anss:
    print(v)
# Original solution
from collections import deque
import sys
import bisect
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
n = int(eval(input()))
a = list(map(int, input().split()))
edges = [[] for _ in range(n)]
for _ in range(n-1):
    u, v = list(map(int, input().split()))
    edges[u-1].append(v-1)
    edges[v-1].append(u-1)

d = [0 for _ in range(n)]
memo = [[] for _ in range(n)]
seen = [False for _ in range(n)]
que = deque()
que.append(0)
memo[0] = [a[0]]
d[0] = 1
seen[0] = True

while len(que):
    cur = que.popleft()
    for to in edges[cur]:
        if not seen[to]:
            seen[to] = True
            memo[to] = memo[cur].copy()
            if memo[cur][-1] < a[to]:
                d[to] = d[cur] + 1
                memo[to].append(a[to])
            else:
                d[to] = d[cur]
                memo[to][bisect.bisect_left(memo[to], a[to])] = a[to]
            que.append(to)

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

# Optimized solution
from collections import deque
import sys
import bisect
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
n = int(eval(input()))
a = list(map(int, input().split()))
edges = [[] for _ in range(n)]
for _ in range(n-1):
    u, v = list(map(int, input().split()))
    edges[u-1].append(v-1)
    edges[v-1].append(u-1)

d = [0 for _ in range(n)]
memo = [[] for _ in range(n)]
seen = [False for _ in range(n)]
que = deque()
que.append(0)
memo[0] = [a[0]]
d[0] = 1
seen[0] = True

while len(que):
    cur = que.popleft()
    for to in edges[cur]:
        if not seen[to]:
            seen[to] = True
            memo[to] = memo[cur].copy()
            if memo[cur][-1] < a[to]:
                d[to] = d[cur] + 1
                memo[to].append(a[to])
            else:
                d[to] = d[cur]
                memo[to][bisect.bisect_left(memo[to], a[to])] = a[to]
            que.append(to)
    memo[cur] = []

for i in range(n):
    print((d[i]))
# Original solution
from bisect import bisect_left
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N = int(eval(input()))
a = list(map(int, input().split()))
G = [[] for _ in range(N)]
for _ in range(N-1):
    u, v = list(map(int, input().split()))
    u -= 1
    v -= 1
    G[u].append(v)
    G[v].append(u)
lis = [float('inf')] * N
ans = [0] * N
visited = [False] * N

def dfs(v):
    visited[v] = True
    i = bisect_left(lis, a[v])
    tmp = lis[i]
    lis[i] = a[v]
    ans[v] = bisect_left(lis, float('inf'))
    for c in G[v]:
        if visited[c]:
            continue
        dfs(c)
    lis[i] = tmp

dfs(0)
print(('\n'.join(map(str, ans))))

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

N = int(eval(input()))
a = list(map(int, input().split()))
G = [[] for _ in range(N)]
for _ in range(N-1):
    u, v = list(map(int, input().split()))
    u -= 1
    v -= 1
    G[u].append(v)
    G[v].append(u)
lis = [float('inf')] * N
ans = [0] * N

def dfs(v, p):
    i = bisect_left(lis, a[v])
    tmp = lis[i]
    lis[i] = a[v]
    ans[v] = bisect_left(lis, float('inf'))
    for c in G[v]:
        if c == p:
            continue
        dfs(c, v)
    lis[i] = tmp

dfs(0, -1)
print(('\n'.join(map(str, ans))))
# Original solution
from bisect import bisect_left


def main():
    N = int(eval(input()))
    A = list(map(int, input().split()))
    adj = [set() for _ in range(N)]
    for i in range(N-1):
        u, v = list(map(int, input().split()))
        adj[u-1].add(v-1)
        adj[v-1].add(u-1)
    ans = [0] * N
    q = [(0, -1, [], True)]
    while len(q):
        cur, prev, lis, override = q.pop()
        idx = bisect_left(lis, A[cur])
        if override:
            nxt_lis = lis
        else:
            nxt_lis = list(lis)
        if idx == len(nxt_lis):
            nxt_lis.append(A[cur])
        else:
            nxt_lis[idx] = A[cur]
        ans[cur] = len(nxt_lis)
        nxt_override = (cur != 0)
        for nxt in adj[cur]:
            if nxt == prev:
                continue
            q.append((nxt, cur, nxt_lis, nxt_override))
            nxt_override = False
    for i in range(N):
        print((ans[i]))


if __name__ == "__main__":
    main()


# Optimized solution
from bisect import bisect_left


def main():
    N = int(eval(input()))
    A = list(map(int, input().split()))
    adj = [set() for _ in range(N)]
    for i in range(N-1):
        u, v = list(map(int, input().split()))
        adj[u-1].add(v-1)
        adj[v-1].add(u-1)
    ans = [0] * N
    q = [(0, -1, [], 0)]
    history = []
    while len(q):
        cur, prev, lis, depth = q.pop()
        while depth < len(history):
            pos, val = history.pop()
            if val is None:
                lis.pop()
            else:
                lis[pos] = val
        idx = bisect_left(lis, A[cur])
        if idx == len(lis):
            history.append((idx, None))
            lis.append(A[cur])
        else:
            history.append((idx, lis[idx]))
            lis[idx] = A[cur]
        ans[cur] = len(lis)
        for nxt in adj[cur]:
            if nxt == prev:
                continue
            q.append((nxt, cur, lis, depth+1))
    for i in range(N):
        print((ans[i]))


if __name__ == "__main__":
    main()
# Original solution
import bisect
import sys
sys.setrecursionlimit(10**7)

def dfs(v,l,tr):
  ans[v]=l
  for u in g[v]:
    if checked[u]==0:
      checked[u]=1
      pos=bisect.bisect_left(tr,arr[u])
      if pos==l:
        dfs(u,l+1,tr+[arr[u]])
      elif tr[pos]==arr[u]:
        dfs(u,l,tr)
      else:
        dfs(u,l,tr[:pos]+[arr[u]]+tr[pos+1:])

n=int(eval(input()))
arr=[0]+list(map(int,input().split()))
g=[[] for _ in range(n+1)]
for _ in range(n-1):
  a,b=list(map(int,input().split()))
  g[a].append(b)
  g[b].append(a)
ans=[0]*(n+1)
checked=[0]*(n+1)
checked[1]=1
dfs(1,1,[arr[1]])
for i in range(1,n+1):
  print((ans[i]))

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

def dfs(v):
  pos=bisect.bisect_left(dp,arr[v])
  changes.append((pos,dp[pos]))
  dp[pos]=arr[v]
  ans[v]=bisect.bisect_left(dp,10**18)
  for u in g[v]:
    if checked[u]==0:
      checked[u]=1
      dfs(u)
  pos,val=changes.pop()
  dp[pos]=val

n=int(eval(input()))
arr=[0]+list(map(int,input().split()))
g=[[] for _ in range(n+1)]
for _ in range(n-1):
  a,b=list(map(int,input().split()))
  g[a].append(b)
  g[b].append(a)
ans=[0]*(n+1)
checked=[0]*(n+1)
checked[1]=1
dp=[10**18 for _ in range(n+1)]
changes=[]
dfs(1)
for i in range(1,n+1):
  print((ans[i]))
# Original solution
import queue
n = int(eval(input()))
a = list(map(int,input().split()))
way = [[] for i in range(n)]
for i in range(n-1):
    u,v = list(map(int,input().split()))
    u,v = u-1,v-1
    way[u].append(v)
    way[v].append(u)

stst = [[] for i in range(n)]
stst[0] = [a[0]]
q = queue.Queue()
for i in way[0]:
    q.put((i,0))

while not q.empty():
    i,pi = q.get()
    for j in way[i]:
        if pi == j:
            continue
        q.put((j,i))
    stst[i] = stst[pi]+[a[i]]

def lenlis(arr):
    mns = [10**18 for i in range(len(arr)+2)]
    mns[0] = 0
    mai = 0
    for i in arr:
        for j in range(len(arr)):
            if i > mns[j]:
                if i < mns[j+1]:
                    mns[j+1] = i
                    break
            else:
                break
    return mns.index(10**18)-1

for i in stst:
    print((lenlis(i)))


# Optimized solution
import queue
inf = 10**18
n = int(eval(input()))
a = list(map(int,input().split()))
way = [[] for i in range(n)]
for i in range(n-1):
    u,v = list(map(int,input().split()))
    u,v = u-1,v-1
    way[u].append(v)
    way[v].append(u)

def Mnsr(ni,mns):
    mnsi = mns + [inf]
    l = 0
    r = len(mns)
    while l < r:
        mid = (r-l)//2+l
        if ni < mnsi[mid]:
            r = mid
        else:
            l = mid+1

    if not mnsi[l-1] == ni:
        mnsi[l] = ni
    return mnsi

def ansfind(arr):
    l = 0
    r = len(arr)-1
    while l < r:
        mid = l + (r-l)//2
        if arr[mid] == inf:
            r = mid
        else:
            l = mid+1
    return l-1


ans = [1 for i in range(n)]
q = queue.Queue()
for i in way[0]:
    q.put((i,0,Mnsr(a[i],[0,a[0],inf])))

while not q.empty():
    i,pi,mns = q.get()
    ans[i] = ansfind(mns)
    for j in way[i]:
        if pi == j:
            continue
        q.put((j,i,Mnsr(a[j],mns)))

for i in ans:
    print(i)
# Original solution
import sys
sys.setrecursionlimit(10**9)
from collections import defaultdict,deque
import bisect
input = sys.stdin.readline

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

g = defaultdict(list)
for i in range(N-1):
    u, v = list(map(int,input().split()))
    g[u].append(v)
    g[v].append(u)

def eulerTour(g,s):
    n = len(g)
    dq = [s]
    ls = [-1]*(n+1)
    rs = [-1]*(n+1)
    index = []
    visited = [False]*(n+1)
    def dfs(v):
        visited[v] = True
        ls[v] = len(index)
        index.append(v)
        for nv in g[v]:
            if not visited[nv]:
                dfs(nv)
        rs[v] = len(index)
        index.append(v)
    dfs(s)
    return ls,rs,index

ls,rs,index = eulerTour(g,1)

inf = 10**10
l = [inf] * (N+1)

ans = [0] * (N+1)
ans[1] = 1

visited = [False]*(N+1)
rollback = []

for v in index:
    if visited[v]:
        i, pa = rollback.pop()
        l[i] = pa
    else:
        A = a[v-1]
        i = bisect.bisect_left(l,A)
        rollback.append((i,l[i]))
        l[i] = A
        ans[v] = l.index(inf)
        visited[v] = True

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







# Optimized solution
import sys
sys.setrecursionlimit(10**9)
from collections import defaultdict,deque
import bisect
input = sys.stdin.readline

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

g = defaultdict(list)
for i in range(N-1):
    u, v = list(map(int,input().split()))
    g[u].append(v)
    g[v].append(u)

def eulerTour(g,s):
    n = len(g)
    dq = [s]
    ls = [-1]*(n+1)
    rs = [-1]*(n+1)
    index = []
    visited = [False]*(n+1)
    def dfs(v):
        visited[v] = True
        ls[v] = len(index)
        index.append(v)
        for nv in g[v]:
            if not visited[nv]:
                dfs(nv)
        rs[v] = len(index)
        index.append(v)
    dfs(s)
    return ls,rs,index

ls,rs,index = eulerTour(g,1)
dq = deque([1])
visited = [False]*(N+1)

inf = 10**10
l = [inf] * (N+1)

ans = [0] * (N+1)
ans[1] = 1

visited = [False]*(N+1)
rollback = []

k = 1
for v in index:
    if visited[v]:
        i, pa = rollback.pop()
        l[i] = pa
        if pa == inf:
            k -= 1
    else:
        A = a[v-1]
        i = bisect.bisect_left(l,A)
        rollback.append((i,l[i]))
        if k <= i:
            k += 1
        l[i] = A
        #ans[v] = l.index(inf)
        ans[v] = k
        visited[v] = True


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