We have a tree with N vertices, whose i-th edge connects Vertex u_i and Vertex v_i.
Vertex i has an integer a_i written on it.
For every integer k from 1 through N, solve the following problem:
 - We will make a sequence by lining up the integers written on the vertices along the shortest path from Vertex 1 to Vertex k, in the order they appear. Find the length of the longest increasing subsequence of this sequence.
Here, the longest increasing subsequence of a sequence A of length L is the subsequence A_{i_1} , A_{i_2} , ... , A_{i_M} with the greatest possible value of M such that 1 \leq i_1 < i_2 < ... < i_M \leq L and A_{i_1} < A_{i_2} < ... < A_{i_M}.

-----Constraints-----
 - 2 \leq N \leq 2 \times 10^5
 - 1 \leq a_i \leq 10^9
 - 1 \leq u_i , v_i \leq N
 - u_i \neq v_i
 - The given graph is a tree.
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
a_1 a_2 ... a_N
u_1 v_1
u_2 v_2
:
u_{N-1} v_{N-1}

-----Output-----
Print N lines. The k-th line, print the length of the longest increasing subsequence of the sequence obtained from the shortest path from Vertex 1 to Vertex k.

-----Sample Input-----
10
1 2 5 3 4 6 7 3 2 4
1 2
2 3
3 4
4 5
3 6
6 7
1 8
8 9
9 10

-----Sample Output-----
1
2
3
3
4
4
5
2
2
3

For example, the sequence A obtained from the shortest path from Vertex 1 to Vertex 5 is 1,2,5,3,4. Its longest increasing subsequence is A_1, A_2, A_4, A_5, with the length of 4.

Difficulty: interview

Starter code:

Solutions:
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(input())
arr=[0]+list(map(int,input().split()))
g=[[] for _ in range(n+1)]
for _ in range(n-1):
    a,b=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])

from bisect import bisect_left
from collections import deque
import sys

sys.setrecursionlimit(200001)

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)

INF = 10**11
ans = [0]*N
dp = []###INFは空欄として扱って良い
stack = deque([])

def LISonTree(num,pre):
    ###num: 頂点番号
    ###pre: 1つ前にいた頂点番号
    p = bisect_left(dp,a[num])

    ###
    #print(p)
    ###

    if p >= len(dp):
        stack.appendleft((len(dp),INF))
        dp.append(a[num])
    else:
        stack.appendleft((p,dp[p]))
        dp[p] = a[num]
        
    
    q = bisect_left(dp,INF)
    ans[num] = q

    ###
    #print(num,'dp',dp)
    #print(num,'ans',ans)
    ###

    for x in graph[num]:
        if x == pre:
            continue
        LISonTree(x,num)
    
    changed_p, changed_v = stack.popleft()

    dp[changed_p] = changed_v

    ###
    #print(num,'dp',dp)
    ###

LISonTree(0,-1)
#print(ans)

for y in ans:
    print(y)

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')

def __starting_point():
    main()
__starting_point()

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations
def run():
    N = int(input())
    A = [0] + list(map(int, sysread().split()))
    to = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u,v = map(int, sysread().split())
        to[u].append(v)
        to[v].append(u)
    seen = [False] * (N+1)
    dp = [float('inf')] * (N+2)
    dp[0] = -float('inf')
    ddp2 = [0]
    paths = []
    actions = []# (idx, pre, pro)
    ans = [0] * (N+1)
    def dfs(node, parent=None):

        a = A[node]
        seen[node] = True
        if parent == None:
            actions.append((1, dp[1], a, 1))
            dp[1] = a
            ddp2[0] += 1
        else:
            idx = bin_search(dp, a)
            if dp[idx] == float('inf'):
                actions.append((idx, dp[idx], a, 1))
                ddp2[0] += 1
            else:
                actions.append((idx, dp[idx], a, 0))
            dp[idx] = a
        ans[node] = ddp2[0]
        for next in to[node]:
            if not seen[next]:
                dfs(next, node)

        idx, pre, pro, change = actions.pop()
        dp[idx] = pre
        ddp2[0] -= change

    dfs(1)
    for s in ans[1:]:
        print(s)
    return None

def bin_search(A, x):
    '''
    return index which is lowest in values more than or equal to x
    '''
    low = 0
    high = len(A) - 1
    c = (low + high) // 2
    if A[-1] < x: return float('inf')
    while high - low > 1:
        if A[c] < x:
            low = c
            c = (low + high) // 2

        elif A[c] > x:
            high = c
            c = (high + low) // 2
        else:
            return c
    return high

def __starting_point():
    run()
__starting_point()

from bisect import bisect_left
import sys
sys.setrecursionlimit(10 ** 9)
n = int(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 = 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, x):
    i = bisect_left(dp, a[p])
    old = dp[i]
    dp[i] = a[p]
    result[p] = bisect_left(dp, INF)
    for j in tree[p]:
        if j != x:
            dfs(j, p)
    dp[i] = old
    

dfs(0, -1)

for i in result:
    print(i)

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

uv = [[] for _ in range(n)]
for _ in range(n-1):
    i, j = map(int, input().split())
    uv[i-1].append(j-1)
    uv[j-1].append(i-1)

# DFS
# 頂点iが未探索の時、ans[i] = -1
ans = [-1 for _ in range(n)]
ans[0] = 1
# dp[i] = 長さi+1のLISの最後尾の最小値
dp = [a[0]]
# history[(i, j)]のとき、変更前はdp[i] = j
# stackとして使用
history = []
# 頂点parents[i] = iの親
parents = [-1 for _ in range(n)]

todo = []
for i in uv[0]:
    todo.append(i)
    parents[i] = 0

while True:
    i = todo.pop(-1)
    
    # ans[i]を求める
    if dp[-1] < a[i]:
        dp.append(a[i])
        history.append((-1, 0))
    else:
        # dpの変更点を二分探索
        start = 0
        stop = len(dp) - 1
        flag = True
        while start < stop:
            center = (start + stop) // 2
            if dp[center] < a[i]:
                start = center + 1
            elif dp[center] > a[i]:
                stop = center
            else:
                flag = False
                break
        if flag and dp[start] > a[i]:
            history.append((start, dp[start]))
            dp[start] = a[i]
        else:
            history.append((-2, 0))
    ans[i] = len(dp)

    # todoに追加
    for j in uv[i]:
        if ans[j] == -1:
            todo.append(j)
            parents[j] = i

    if len(todo) == 0:
        break

    # back
    j = i
    while parents[todo[-1]] != j:
        k = history.pop(-1)
        if k[0] == -2:
            None
        elif k[0] == -1:
            dp.pop(-1)
        else:
            dp[k[0]] = k[1]
        j = parents[j]

for i in ans:
    print(i)

import sys
import bisect
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(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]))


def __starting_point():
    main()

__starting_point()

import bisect
I = [int(_) for _ in open(0).read().split()]
N = I[0]
A = [0] + I[1:1 + N]
U = [0] + I[1 + N::2]
V = [1] + I[2 + N::2]
G = [set() for _ in range(N + 1)]
for u, v in zip(U, V):
    G[u].add(v)
    G[v].add(u)
ans = [10**10] * (N + 1)
stack = [(0, 1, 1, A[1], 0)]
dp = [-10 ** 10] + [10 ** 10] * N
while stack:
    i, j, p, q, d = stack.pop()
    if d:
        dp[p] = q
        continue
    stack += [(j, i, p, dp[p], 1)]
    dp[p] = q
    ans[j] = bisect.bisect_left(dp, 10 ** 10) - 1
    while G[j]:
        k = G[j].pop()
        if i == k:
            continue
        q = A[k]
        p = bisect.bisect_left(dp, q)
        stack += [(j, k, p, q, 0)]
print(*ans[1:], sep='\n')


#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf

import math
import bisect

class Tree:
    """
    node id starts from 1
    """

    DUMMY = 0 # used as dummy_node_id and dummy_node_value

    def __init__(self, num_node, node_values):
        self.node_values = [-1] + node_values # [0] is dummy
        self.edges = [None] * (num_node + 1) # [0] is dummy, var[a] = set of links
        for i, _ in enumerate(self.edges):
            self.edges[i] = set()
        self.seq = [self.DUMMY] * num_node

        self.dp = [math.inf] * (num_node + 1)
        self.dp[0] = -1 * math.inf
        self.ans = [0] * (num_node + 1) # [0] is dummy


    def node_values(self, node_values):
        self.node_values = [-1] + node_values # [0] is dummy

    def make_edge(self, a, b):
        self.edges[a].add(b)
        self.edges[b].add(a)

    def dps(self, node_id, prev=0, depth=0):
        # process
        value = self.node_values[node_id]
        key = bisect.bisect_left(self.dp, value)
        old_value = self.dp[key]
        self.dp[key] = value
        self.ans[node_id] = max(key, self.ans[prev])
        # recursive
        for to in self.edges[node_id]:
            if to == prev:
                continue
            self.dps(to, node_id, depth + 1)
        # recursive back
        self.dp[key] = old_value

def __starting_point():
    num_node = int(input())
    node_values = list(map(int, input().split()))
    tree = Tree(num_node, node_values)
    for i in range(num_node - 1):
        frm, to = list(map(int, input().split()))
        tree.make_edge(frm, to)
    tree.dps(1)
    for a in tree.ans[1:]:
        print(a)



__starting_point()

import sys
sys.setrecursionlimit(10**8)
N = int(input())
A = list(map(int,input().split()))
UV = [tuple(map(int,input().split())) for i in range(N-1)]
es = [[] for _ in range(N)]
for u,v in UV:
    u,v = u-1,v-1
    es[u].append(v)
    es[v].append(u)

from bisect import bisect_left
lis = [A[0]]
stack = []
ans = [1] * N
def dfs(v,p=-1):
    for to in es[v]:
        if to==p: continue
        i = bisect_left(lis, A[to])
        if i == len(lis):
            stack.append((i,-1))
            lis.append(A[to])
        else:
            stack.append((i,lis[i]))
            lis[i] = A[to]
        ans[to] = len(lis)

        dfs(to,v)

        i,a = stack.pop()
        if a < 0:
            lis.pop()
        else:
            lis[i] = a

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

import sys
import bisect  # 二分法


MAX_N = 200005
INF = 10**9 + 5

sys.setrecursionlimit(MAX_N)

N = int(sys.stdin.readline())
A = [int(x) for x in sys.stdin.readline().split()]
E = [[] for _ in range(N)]  # 辺の情報

for _ in range(N-1):
    u, v = map(int, sys.stdin.readline().split())
    E[u-1].append(v-1)
    E[v-1].append(u-1)

lis = [INF] * N
ans = [0] * N 

def dfs(u,r=-1):

    # u を訪れたときの処理
    i = bisect.bisect_left(lis, A[u])  # 
    old = lis[i]  # 書き換え前の値を一時保存
    lis[i] = A[u]

    for v in E[u]:
        if v == r: continue  # 親は無視

        dfs(v,u)
    
    ans[u] = bisect.bisect_left(lis,INF-1)
    lis[i] = old  # 書き換え前の状態に戻す

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

# LIS on Tree

from collections import deque
import bisect
import sys
sys.setrecursionlimit(10**7)

N = int(input())
V = list(map(int, input().split()))
V.insert(0, 0)
visited = [False for i in range(N+1)]
inf = 10**18
dp = [inf for i in range(N+1)]
ans = [-1 for i in range(N+1)]
stack = deque()

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


def dfs(s_node):
    visited[s_node] = True
    # dp値の更新
    value = V[s_node]
    index = bisect.bisect_left(dp, value)
    old_value = dp[index]
    dp[index] = value
    ans[s_node] = bisect.bisect_right(dp, inf-1)
    stack.append((index, old_value, value))
    for child in G[s_node]:
        if visited[child] == False:
            dfs(child)
    # 帰りがけにバックトラックを行う
    index, old_value, value = stack.pop()
    dp[index] = old_value


dfs(1)

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

import sys
sys.setrecursionlimit(1000000)
from bisect import bisect, bisect_left
def dfs(vertex):
  visited[vertex] = True
  value = a[vertex]
  j = bisect(dp, value)
  previous = dp[j]
  if dp[j-1] != value: # strict increasing
    dp[j] = value
  ans[vertex] = bisect_left(dp, float("inf"))-1
  for node in adjacent[vertex]:
    if not visited[node]:
      dfs(node)
  dp[j] = previous
  return
n = int(input())
a = list(map(int, input().split()))
adjacent = {i: [] for i in range(n)}
for _ in range(n-1):
  node1, node2 = map(int, input().split())
  node1 -= 1
  node2 -= 1
  adjacent[node1].append(node2)
  adjacent[node2].append(node1)
visited = [False]*n
ans = [0]*n
dp = [float("inf") for _ in range(n+1)]
dp[0] = float("-inf")
dfs(0)
[print(value) for value in ans]

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

N = int(input())
A = list(map(int, input().split()))
G = [[] for _ in range(N)]

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

INF = 10**9+1

#a = [~0,0]
q = [0]    # ~0=-1なのだが、とにかく0を打ち消す方向をやるよ、と言うこと。うまい。
dp = [INF]*N  # LIS
ans = [0]*N   # iにおけるLISの長さ
lis_len = 0   # 持ち回ってるLIS長さ変数。dpをsearchしても求まるけど、安易に野郎
idx = [-1]*N  # iのときの操作したIDX
old = [-1]*N  # iのときに操作する前の値。Rollbackする時に使う
prev = [-1]*N # 自分の呼び出しもと。グラフの行ってこいを抑止するため。

ss = 0
from bisect import bisect_left
while q:
  now = q.pop()
  # 普通のdfs
  if now >= 0:
    a = A[now]
    # LIS管理のdpに今回操作する対象のIDXを探索
    idx[now] = bisect_left(dp,a)
    # 操作前の値とIDXを保存する
    iv = idx[now]
    old[now] = dp[idx[now]]
    x = old[now]
    # LIS管理dpのVALUEがINFだったら、今回で長さが伸びるってこと
    if x == INF:
      lis_len += 1
    dp[iv] = a
    ans[now] = lis_len

    for nxt in G[now]:
      if nxt == prev[now]:
        continue
      prev[nxt] = now
      #q.append(~nxt)
      #q.append(nxt)
      q.append((-1)*nxt)
      q.append(nxt)
  # nowがゼロ以下なので、DPを一つRollbackする動きをする。
  else:
    #v = ~v # ビット反転だが、これで元のNOWを復元する
    now = (-1)*now
    dp[idx[now]] = old[now]
    x = dp[idx[now]] 
    if x == INF:
      lis_len -= 1
    
#print(*ans,sep="\n")
for a in ans:
  print(a)


# 木によって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')


# coding: utf-8
import sys
from bisect import bisect_left, bisect_right, insort
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = [0] + lr()  # 1-indexed
graph = [[] for _ in range(N+1)]  # 1-indexed
for _ in range(N-1):
    a, b = lr()
    graph[a].append(b)
    graph[b].append(a)

answer = [0] * (N+1)  # 1-indexed
INF = 10 ** 10
parent = [-1] * (N+1)

def dfs(n):
    """answerのリストを更新してからdfsして、oldで戻す"""
    i = bisect_left(dp, INF)
    answer[n] = i
    for c in graph[n]:
        if c == parent[n]:
            continue
        parent[c] = n
        i = bisect_left(dp, A[c])
        old = dp[i]
        dp[i] = A[c]
        dfs(c)
        dp[i] = old

dp = [INF] * (N+1)
dp[0] = A[1]
dfs(1)
for a in answer[1:]:
    print(a)


N=int(input())
A=list(map(int,input().split()))
UV=[list(map(int,input().split())) for i in range(N-1)]
c=[[] for i in range(N)]
for i,j in UV:
    c[i-1].append(j-1)
    c[j-1].append(i-1)
v=[0]*N
d=[10**9+1]*N
stk=[]
ans=[0]*N
from bisect import bisect_left
import sys
sys.setrecursionlimit(10**9)
def dfs(p,l):
    i=bisect_left(d,A[p])
    stk.append((i,d[i]))
    d[i]=A[p]
    if i==l:
        l+=1
    ans[p]=l
    for n in c[p]:
        if v[n]==0:
            v[n]=1
            dfs(n,l)
    i,x=stk.pop()
    d[i]=x
v[0]=1
dfs(0,0)
print(*ans,sep='\n')

#!python3

import sys
sys.setrecursionlimit(10 ** 6)

import numpy as np


INF = 10 ** 10

# input
N = int(input())
A = list(map(int, input().split()))
uv = [list(map(int, input().split())) for _ in range(N - 1)]

# link
link = [[] for _ in range(N + 1)]
for u, v in uv:
    link[u].append(v)
    link[v].append(u)


def dfs(l, dp, pre, v):
    # LIS
    idx = np.searchsorted(dp, A[v - 1])
    l[v] = max(idx, l[pre])
    bef = dp[idx]
    dp[idx] = A[v - 1]
    
    for x in link[v]:
        if x != pre:
            dfs(l, dp, v, x)

    dp[idx] = bef


def main():
    l = [0] * (N + 1)
    dp = np.full(N + 1, INF)
    dp[0] = 0
    dfs(l, dp, 0, 1)
    for ans in l[1:]:
        print(ans)


def __starting_point():
    main()

__starting_point()

import sys
sys.setrecursionlimit(10**7)
from bisect import bisect_left as bl
def main(n,a):
  ans=[0]*n
  ki=[[] for _ in range(n)]
  for _ in range(n-1):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    ki[u].append(v)
    ki[v].append(u)
  inf=float('inf')
  p={}
  dp=[inf]*(n+1)
  dp[0]=0
  # dp[i]:長さiのLISの末尾の数値の最小値
  maxa=max(a)+1

  def dfs(v,p,dp):
    x=a[v]
    idx=bl(dp,x)
    tmp=dp[idx]
    dp[idx]=x
    # ans[v]=idx こっちだと頂点vで終わるLISの長さになる。下が正しい
    ans[v]=bl(dp,maxa)-1
    for nv in ki[v]:
      if nv==p:continue
      dfs(nv,v,dp)
    dp[idx]=tmp
  dfs(0,-1,dp)
  print(*ans,sep='\n')

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


#MLE注意！0や1のケースに注意

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    a = list(map(int, input().split()))
    adj = [[] for _ in range(n)] #頂点数, 場合によって変える
    for _ in range(n-1):
        c,b = list(map(int, input().split()))
        adj[c-1].append(b-1)
        adj[b-1].append(c-1)

    # 頂点1も含む
    res = [0]*n
    res[0] = 1

    def dfs(v, par, L):
        if v != 0:
            if a[v] > L[-1]:
                temp = -1
                L.append(a[v])
            else:
                temp = bisect_left(L, a[v])
                pre = L[temp]
                L[temp] = a[v]
        res[v] = len(L)
        for nv in adj[v]:
            if nv == par:
                continue
            dfs(nv, v, L)
        if v != 0:
            if temp == -1:
                L.pop(-1)
            else:
                L[temp] = pre

    L = [a[0]]
    dfs(0, -1, L)
    for i in range(n):
        print((res[i]))

def __starting_point():
    main()

__starting_point()

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')


from bisect import bisect_left
from collections import defaultdict as dd
N = int(input())
As = list(map(int, input().split()))
Es = dd(dict)
for _ in range(N-1):
    f, t = list(map(int, input().split()))
    Es[f-1][t-1] = Es[t-1][f-1] = 1

INF = float('inf')
RET = 0
PROC = 1

stack = []
lismin = [INF] * N
anss = [INF] * N
visited = [False] * N

stack.append((RET, 0, INF))
stack.append((PROC, 0, 0))
while stack:
    cmd, *v = stack.pop()
    if cmd == RET:
        i, backup = v
        lismin[i] = backup
    else:
        node, i = v
        lismin[i] = As[node]
        anss[node] = bisect_left(lismin, INF)
        visited[node] = True
        for to in list(Es[node].keys()):
            if not visited[to]:
                x = bisect_left(lismin, As[to])
                stack.append((RET, x, lismin[x]))
                stack.append((PROC, to, x))
for ans in anss:
    print(ans)



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

def solve(G, a, lis, pre, p, ans):
    target = a[p]
    idx = bisect_left(lis, target)
    frm = lis[idx]
    to = target
    lis[idx] = to
    ans[p] = bisect_left(lis, float("inf"))
    for v in G[p]:
        if v == pre:
            continue
        solve(G, a, lis, p, v, ans)
    lis[idx] = frm

def main():
    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, v = u-1, v-1
        G[u].append(v)
        G[v].append(u)
    lis = [float("inf")]*(n+1)
    ans = [None]*n
    solve(G, a, lis, -1, 0, ans)
    for v in ans:
        print(v)

def __starting_point():
    main()
__starting_point()

import sys
sys.setrecursionlimit(200000)
from collections import deque
from bisect import bisect_left

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


INF = 10 ** 10
done = [False] * N
done[0] = True
lisdp = [INF] * N
lisdp[0] = A[0]
change = [[-1, INF] for i in range(N)] #index, original
change[0] = [0, INF]
lisl = [0] * N
lisl[0] = 1

def dfs(v):
	for nv in adj[v]:
		if done[nv]:
			continue
		done[nv] = True
		ind = bisect_left(lisdp, A[nv])
		ori = lisdp[ind]
		change[nv] = [ind, ori]
		if ori == INF:
			lisl[nv] = lisl[v] + 1
		else:
			lisl[nv] = lisl[v]
		lisdp[ind] = A[nv]
		dfs(nv)
	lisdp[change[v][0]] = change[v][1]

dfs(0)
for i in range(N):
	print(lisl[i])	

#import numpy as np
#import math
#from decimal import *
#from numba import njit
from bisect import bisect_left

#@njit
def main():
    N = int(input())
    a = list(map(int, input().split()))
    edges = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u,v = list(map(int, input().split()))
        edges[u] += v,
        edges[v] += u,

    ans = [0]*(N+1)
    lastLis = []
    visited = [False]*(N+1)
    parent = {}
    n = 1
    stack = []
    while True:
        #print(n, lastLis, stack)
        if not visited[n]:
            if len(lastLis) == 0 or a[n-1] > lastLis[-1]:
                lastLis.append(a[n-1])
                stack += (len(lastLis)-1, -1),
            else:
                index = bisect_left(lastLis, a[n-1])
                stack += (index, lastLis[index]),
                lastLis[index] = a[n-1]
            ans[n] = len(lastLis)
            visited[n] = True
        hasNext = False
        for d in edges[n]:
            if not visited[d]:
                parent[d] = n
                n = d
                hasNext = True
        if not hasNext:
            if n == 1:
                n = 0
                break
            n = parent[n]
            # 巻き戻し
            index, value = stack.pop(len(stack)-1)
            if value < 0:
                lastLis.pop(index)
            else:
                lastLis[index] = value

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




main()


import sys
input=sys.stdin.readline
sys.setrecursionlimit(10000000)

from bisect import bisect_left,bisect_right
n=int(input())
a=list(map(int,input().split()))
edge=[[]for i in range(n)]
for i in range(n-1):
  u,v=map(int,input().split())
  edge[u-1].append(v-1)
  edge[v-1].append(u-1)
ans=[-1]*n
dp=[10**18]*n

#オイラーツアー
#n=頂点数、s=始点、edge=隣接リスト
def EulerTour(n,s,e):
  EulerTour_list=[]
  def EulerTour_dfs(i,root):
    EulerTour_list.append(i)
    idx=bisect_left(dp,a[i])
    bef=dp[idx]
    dp[idx]=a[i]
    ans[i]=bisect_left(dp,10**18)
    for j in e[i]:
      if j!=root:
        EulerTour_dfs(j,i)
    if root!=-1:
      EulerTour_list.append(root)
      dp[idx]=bef
  EulerTour_dfs(s,-1)
  return EulerTour_list

EulerTour(n,0,edge)
print(*ans,sep="\n")


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")

from sys import setrecursionlimit
from bisect import bisect_left

setrecursionlimit(10 ** 6)
INF = float("inf")

N, *I = map(int, open(0).read().split())
A, UV = I[:N], I[N:]

E = [[] for _ in range(N + 1)]
for u, v in zip(*[iter(UV)] * 2):
    E[u - 1].append(v - 1)
    E[v - 1].append(u - 1)

dp = [INF] * N
ans = [0] * N
def dfs(cur, visited):
    idx = bisect_left(dp, A[cur])
    pre = dp[idx]
    dp[idx] = A[cur]
    ans[cur] = bisect_left(dp, INF)
    for c in E[cur]:
        if c != visited:
            dfs(c, cur)
    dp[idx] = pre

dfs(0, -1)
for a in ans:
    print(a)

import sys
from bisect import bisect_left
def main():
    sys.setrecursionlimit(202020)
    N = int(input())
    A = [0] + list(map(int, input().split()))
    G = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u, v = list(map(int, input().split()))
        G[u].append(v)
        G[v].append(u)
    L = [A[1]]
    Ans = [0] * (N+1)
    def dfs(v):
        Ans[v] = len(L)
        for u in G[v]:
            G[u].remove(v)
            Au = A[u]
            if Au > L[-1]:
                L.append(Au)
                dfs(u)
                del L[-1]
            else:
                idx = bisect_left(L, Au)
                old = L[idx]
                L[idx] = Au
                dfs(u)
                L[idx] = old
    dfs(1)
    print(("\n".join(map(str, Ans[1:]))))

main()


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

import sys
sys.setrecursionlimit(10**6)

lastdp=[10**9+1]*n
recode=[[10**9+1]for i in range(n)]
ans=[0]*n
from bisect import bisect_left
def rec(me,parent):
    nonlocal lastdp
    a=A[me]
    point=bisect_left(lastdp,a)
    recode[point].append(a)
    lastdp[point]=a
    tmpans=bisect_left(lastdp,10**9+1)
    ans[me]=tmpans

    for child in g[me]:
        if child!=parent:
            rec(child,me)

    recode[point].pop()
    lastdp[point]=recode[point][-1]
    return

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


import sys
from bisect import bisect_left as bisect
input = sys.stdin.readline
sys.setrecursionlimit(2 * 10**6)


def inpl():
    return list(map(int, input().split()))


class solve:
    def __init__(self, N):
        self.ans = [0] * N
        self.DP = []

    def recur(self, i, pi=-1):
        # DPテーブルを更新し、答えを求める。
        # また、巻き戻す値を覚える。
        rev_i = bisect(self.DP, self.A[i])
        if rev_i == len(self.DP):
            self.DP.append(self.A[i])
            rev_v = None
        else:
            rev_v = self.DP[rev_i]
            self.DP[rev_i] = self.A[i]

        self.ans[i] = len(self.DP)

        for nv in self.edges[i]:
            if nv != pi:
                self.recur(nv, i)

        # 巻き戻す。.
        if rev_v is None:
            self.DP.pop()
        else:
            self.DP[rev_i] = rev_v

        return


def main():
    N = int(input())
    S = solve(N)
    S.A = inpl()
    S.edges = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v = inpl()
        S.edges[u - 1].append(v - 1)
        S.edges[v - 1].append(u - 1)

    S.recur(0)

    print(*S.ans, sep='\n')
    # print(edges)
    # print(parent)
    # print(DPs)


def __starting_point():
    main()

__starting_point()

import sys
from bisect import bisect_left
sys.setrecursionlimit(1000000)
INF = pow(10, 10)

changed = []
input = sys.stdin.readline
N = int(input())
A = [int(a) for a in input().split()]
Edge = [[] for _ in range(N)]
for _ in range(N-1):
    u, v = map(int, input().split())
    Edge[u-1].append(v-1)
    Edge[v-1].append(u-1)
LIS = [INF] * N

def dfs(i, pre, Ans):
    changeID = bisect_left(LIS, A[i])
    changed.append((changeID, LIS[changeID]))
    LIS[changeID] = min(A[i], LIS[changeID])
    #print(i, LIS)
    #print(changed)
    Ans[i] = bisect_left(LIS, INF) 
    for nextN in Edge[i]:
        if nextN != pre: dfs(nextN, i, Ans)
    backID, backV = changed.pop()
    LIS[backID] = backV
    return 0

def solve():
    Ans = [1] * N
    dfs(0, 0, Ans)
    print("\n".join(map(str, Ans)))
    
    return 0

def __starting_point():
    solve()
__starting_point()

from bisect import bisect_left

INF = 10 ** 9

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

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

ans = [0] * N
LIS = [INF] * (N+1)
rewinder = []

parent = [-1] * N
stack = [0]
while stack:
    node = stack.pop()
    for next_node in adj[node]:
        if ans[next_node] == 0:
            parent[next_node] = node
            stack.append(next_node)

    while rewinder and rewinder[-1][0] != parent[node]:
        _, index, prev_value = rewinder.pop()
        LIS[index] = prev_value
    
    index = bisect_left(LIS, As[node])
    rewinder.append((node, index, LIS[index]))
    LIS[index] = As[node]

    ans[node] = bisect_left(LIS, INF)

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

import bisect
import sys
sys.setrecursionlimit(10**7)

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

m = 10**18
dp = [m]*(n+1)
ans = [1]*(n+1)
checked = [False]*(n+1)
checked[1] = True
changes = []

def search(x):
    ind = bisect.bisect_left(dp,a[x])
    changes.append((ind,dp[ind]))
    dp[ind] = a[x]
    ans[x] = bisect.bisect_left(dp,m)
    
    for i in t[x]:
        if not checked[i]:
            checked[i] = True
            search(i)
    
    b,c = changes.pop()
    dp[b] = c
    
search(1)
for i in ans[1:]:
    print(i)

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):
    nonlocal seq
    nonlocal 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]


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')

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

ans = [0] * N
check = [False] * N
check[root] = True

memo = [None] * N

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

def dfs(x):
    tmp = bisect_left(dp, A[x])
    memo[x] = (tmp, dp[tmp])
    dp[tmp] = A[x]
    ans[x] = bisect_left(dp, INF)
    for next_ in G[x]:
        if check[next_]:
            continue
        check[next_] = True
        dfs(next_)
    j, a = memo[x]
    dp[j] = a

dfs(root)

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



## まきもどし？
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
ceil = math.ceil
import sys
sys.setrecursionlimit(10**6)
n = ni()
A = lma()
tree = [[] for i in range(n)]
INF = 10**10
for i in range(n-1):
    u,v = ma();u-=1;v-=1
    tree[u].append(v)
    tree[v].append(u)
#print(tree)
def isok(num,val):##適宜変更
    return num<val
def bisect(ls,val): ##valの関数isok(x,val)がTrueとなる一番右のindex を返す 全部Falseなら-1,Trueならlen(ls)-1
    ok = -1
    ng = len(ls)
    x = (ok+ng)//2
    while ng-ok>1:
        num = ls[x]
        if isok(num,val):
            ok = x
        else:
            ng = x
        x = (ok+ng)//2
    return ok ##一番右のTrueのindex  Trueの個数はok+1こ
def LIS_1(x,ls,right):##right ::これまでわかっている右端
    idx = bisect(ls,x)+1
    if idx+1>right:
        ret= idx+1
    else:
        ret=right
    rewind_idxval.append((idx,ls[idx]))
    ls[idx]=x
    #print(x,ls)
    return ret
def DFS_LIS(prev,ls,right):
    ans[prev]= LIS_1(A[prev],ls,right)
    for node in tree[prev]:
        if not visited[node]:
            visited[node]=True
            DFS_LIS(node,ls,ans[prev])
    #rewind
    idx,pval = rewind_idxval.pop()
    ls[idx] = pval

ans = [0]*n
s = 0
right=0
rewind_idxval=collections.deque()
visited=[False]*n
visited[s]=True
ls=[INF]*n
DFS_LIS(s,ls,right)
#print(ls)
for a in ans :
    print(a)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
import bisect
INF = 2**31 - 1

n = int(input())
A = list(map(int, input().split()))
T = [[] for _ in range(n)]
for _ in range(n-1):
  u, v = map(int, input().split())
  u -= 1
  v -= 1
  T[u].append(v)
  T[v].append(u)
stack = []
L = [INF]*n
ans = [0]*n
def dfs(v, par=-1):
  a = A[v]
  idx = bisect.bisect_left(L, a)
  stack.append((idx, L[idx]))
  L[idx] = a
  ans[v] = bisect.bisect_left(L, INF)
  for nv in T[v]:
    if nv != par:
      dfs(nv, v)
  b, c = stack.pop()
  L[b] = c
dfs(0)
print(*ans, sep="\n")

import sys
import bisect
sys.setrecursionlimit(10**6)

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

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

rooted = [[] for _ in range(n)]
que = [(0, -1)]
while que:
    node, parent = que.pop()
    for child in graph[node]:
        if child != parent:
            rooted[node].append(child)
            # rooted[child].append(node)
            que.append((child, node))
            # print(child + 1, node + 1)

table = [float('inf')] * n
lis = [None] * n
def dfs(node, length=0):
    p = bisect.bisect_left(table, a[node])
    table[p], old = a[node], table[p]
    length = max(p + 1, length)
    for child in rooted[node]:
        dfs(child, length)
    table[p] = old
    lis[node] = length

dfs(0)
print(*map(str, lis), sep="\n")


# F - LIS on Tree
import bisect
import sys
sys.setrecursionlimit(10**7)

INF = 10**18

n = int(input())
a = list(int(x) for x in 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)

def dfs(now, par):
    idx = bisect.bisect_left(dp, a[now])    
    tmp = dp[idx]
    dp[idx] = a[now]
    # 親のLIS以上であれば、その値で更新
    if ans[par] <= idx:
        ans[now] = idx
    # そうでなければ親のLISを引き継ぐ
    else:
        ans[now] = ans[par]

    for i in g[now]:
        if i!=par:
            # 次にみる頂点と、自分（親）の情報を渡す
            dfs(i, now)
    dp[idx] = tmp

ans = [0] * n
dp = [-INF] + [INF] * n
dfs(0, -1)
for a in ans:
    print(a)


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')

import sys
from collections import defaultdict
from bisect import bisect_left
sys.setrecursionlimit(1000000)
input=sys.stdin.readline


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

INF = 10**20
l = [INF]*(N)
q = []
ans = [0]*(N+1)

def dfs(s, root):
    v = bisect_left(l, a[s-1])
    q.append((v, l[v]))
    l[v] = a[s-1]
    ans[s] = bisect_left(l, INF)

    for t in d[s]:
        if t==root:continue
        dfs(t, s)
    
    ba, bb = q.pop()
    l[ba] = bb

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


import sys
import math
import heapq
import bisect
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return map(int, sys.stdin.readline().split())
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())


def FLIST(n):
    res = [1]
    for i in range(1, n+1):
        res.append(res[i-1]*i % DVSR)
    return res


N = II()
AS = list(LI())

MP = {}

MX = 10**10
LIS = [10**10]*N
RES = [1]*N
for i in range(N-1):
    a, b = LI()
    a -= 1
    b -= 1
    if not a in MP:
        MP[a] = []
    if not b in MP:
        MP[b] = []
    MP[a].append(b)
    MP[b].append(a)


def dfs(v, mp, lis, p):
    for u in mp[v]:
        if u != p:
            i = bisect.bisect_left(lis, AS[u])
            bef = lis[i]
            lis[i] = AS[u]
            longest = bisect.bisect_left(lis, MX)
            RES[u] = longest
            dfs(u, mp, lis, v)
            lis[i] = bef


LIS[0] = AS[0]
dfs(0, MP, LIS, -1)

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


import bisect
import sys
sys.setrecursionlimit(10**7)

def dfs(v):
 #DFSの行き(子ノードに下っていくとき)の処理
 pos=bisect.bisect_left(dp,arr[v]) #最長増加部分列で更新する場所を2分探索により求める
 changes.append((pos,dp[pos])) #更新した要素とその値を記録しておく
 dp[pos]=arr[v]
 ans[v]=bisect.bisect_left(dp,10**18) #1からvまでの最長増加部分列の長さは、最長増加部分列の10**18以外の値の個数に等しい
 for u in g[v]:
   if checked[u]==0:
     checked[u]=1
     dfs(u)
 #DFSの戻り(親ノードに上っていくとき)の処理
 pos,val=changes.pop() #頂点vで更新した最長増加部分列の値を元に戻す
 dp[pos]=val

n=int(input())
arr=[0]+list(map(int,input().split()))
g=[[] for _ in range(n+1)]
for _ in range(n-1):
 a,b=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])

import sys
sys.setrecursionlimit(1000000)
from bisect import bisect, bisect_left
def longest_subsequence(sequence):
  subsequence = [float("inf") for _ in range(len(sequence)+1)]
  subsequence[0] = float("-inf")
  for value in sequence:
    j = bisect(subsequence, value)
    if subsequence[j-1] != value: # strict increasing
      subsequence[j] = value
  return bisect_left(dp, float("inf"))-1
# print(longest_subsequence([9, 13, 2, 10, 4, 13, 11, 13]))
# return
def dfs(vertex):
  visited[vertex] = True
  value = a[vertex]
  j = bisect(subsequence, value)
  previous = subsequence[j]
  if subsequence[j-1] != value: # strict increasing
    subsequence[j] = value
  ans[vertex] = bisect_left(subsequence, float("inf"))-1
  for node in adjacent[vertex]:
    if not visited[node]:
      dfs(node)
  subsequence[j] = previous
  return
n = int(input())
a = list(map(int, input().split()))
adjacent = {i: [] for i in range(n)}
for _ in range(n-1):
  node1, node2 = map(int, input().split())
  node1 -= 1
  node2 -= 1
  adjacent[node1].append(node2)
  adjacent[node2].append(node1)
visited = [False]*n
ans = [0]*n
subsequence = [float("inf") for _ in range(n+1)]
subsequence[0] = float("-inf")
dfs(0)
[print(value) for value in ans]

import sys
readline = sys.stdin.readline

sys.setrecursionlimit(10**6)


def main():
    N = int(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


def __starting_point():
    main()

__starting_point()

from collections import deque
import bisect
import sys

sys.setrecursionlimit(200000)

N = int(input())
a = list(map(int, input().split()))
uvs = [list(map(int, input().split())) for _ in range(N-1)]
shortest = [10e+10 for _ in range(N)]
shortest[0] = 0

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

for uv in uvs:
    routes[uv[0]-1].append(uv[1]-1)
    routes[uv[1]-1].append(uv[0]-1)

lis = [10e+100 for _ in range(N)]
minimum = [10e+100 for _ in range(N)]
seen = [False for _ in range(N)]
seen[0] = True

def function(checking):
    insert_posi = bisect.bisect_left(lis, a[checking])
    preserved = lis[insert_posi]
    lis[insert_posi] = a[checking]
    minimum[checking] = bisect.bisect_left(lis, 10e+50)
    for route in routes[checking]:
        if seen[route] == False:
            seen[route] = True
            shortest[route] = shortest[checking]+1
            function(route)
    lis[insert_posi] = preserved
    return
        
function(0)

[print(x) for x in minimum]

import sys
readline = sys.stdin.readline

sys.setrecursionlimit(10 ** 7)


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

    edges = (list(map(int, readline().strip().split())) for _ in range(N-1))

    tree = [[] for _ in range(N)]
    for u, v in edges:
        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


def __starting_point():
    main()

__starting_point()

import sys
sys.setrecursionlimit(10**7)
from bisect import bisect_left
INF=10**18
def dfs(v,p,max_):
    b=bisect_left(dp,a[v])
    memo=(b,dp[b])
    dp[b]=a[v]
    if b>max_:
        max_=b
    ans[v]=max_
    for nv in G[v]:
        if nv==p:
            continue
        dfs(nv,v,max_)
    dp[memo[0]]=memo[1]

N=int(input())
a=list(map(int,input().split()))
G=[[] for i in range(N)]
for i in range(N-1):
    u,v=map(lambda x:int(x)-1,input().split())
    G[u].append(v)
    G[v].append(u)
dp=[INF]*(N+1)
dp[0]=-1
ans=[-1]*N
dfs(0,-1,0)
print(*ans,sep='\n')

# 写経
# https://atcoder.jp/contests/abc165/submissions/12655073
from bisect import bisect_left, bisect_right
import sys

def resolve():
    input = sys.stdin.readline
    sys.setrecursionlimit(10**9)
    INF = float('inf') 
    N = int(input())
    As = list(map(int, input().split()))
    adjL = [[] for _ in range(N)]
    for _ in range(N-1):
        u, v = map(int, input().split())
        u, v = u-1, v-1
        adjL[u].append(v)
        adjL[v].append(u)
    
    dp = [-INF]
    anss = [0] * N
    def dfs(vNow, vPar):
        A = As[vNow]
        if dp[-1] < A:
            dp.append(A)
            tp = 0
        else:
            i = bisect_left(dp, A)
            tp = 1
            iOld, AOld, = i, dp[i]
            dp[i] = A
        anss[vNow] = len(dp) - 1
    
        for v2 in adjL[vNow]:
            if v2 == vPar: continue
            dfs(v2, vNow)
    
        if tp == 0:
            dp.pop()
        else:
            dp[iOld] = AOld
    
    dfs(0, -1)

    print('\n'.join(map(str, anss)))
resolve()

from collections import deque
from bisect import bisect_left as bile

def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    sys.setrecursionlimit(10**6)
    n = int(input())
    arr = list(map(int, input().split()))
    adj = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        adj[a].append(b)
        adj[b].append(a)

    ans = [0]*n
    inf = 1e18
    dp = [inf]*(n+10)
    parent = [-1]*n
    def dfs(s):
        idx = bile(dp, arr[s])
        tmp = dp[idx]
        dp[idx] = arr[s]
        ans[s] = bile(dp, inf)

        for v in adj[s]:
            if v == parent[s]:
                continue
            parent[v] = s
            dfs(v)
        dp[idx] = tmp
        return ans
        
    ans = dfs(0)
    for a in ans:
        print(a)


def __starting_point():
    main()
__starting_point()

import sys
readline = sys.stdin.readline

from bisect import bisect_left

sys.setrecursionlimit(10 ** 7)


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

    edges = (list(map(int, readline().strip().split())) for _ in range(N-1))

    tree = [[] for _ in range(N)]
    for u, v in edges:
        tree[u-1].append(v-1)
        tree[v-1].append(u-1)

    inf = 10 ** 12
    dp = [inf] * (N+1)
    ans = [0] * N

    def dfs(node, parent):
        v = As[node]
        lb = bisect_left(dp, v)
        old = dp[lb]
        dp[lb] = v
        ans[node] = bisect_left(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 __starting_point():
    main()

__starting_point()

import sys
from bisect import bisect_left
sys.setrecursionlimit(10**7)
def input():return sys.stdin.readline().strip()

def main():
    N = int(input())
    A = tuple(map(int, input().split()))

    to = [[] for _ in range(N)]
    for _ in range(N-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        to[u].append(v)
        to[v].append(u)
    
    ans = [0] * N
    dp = []
    def dfs(now, pre):
        a = A[now]
        idx = bisect_left(dp, a)

        if idx == len(dp):
            old = -1
            dp.append(a)
        else:
            old = dp[idx]
            dp[idx] = a
        
        ans[now] = len(dp)

        
        for nv in to[now]:
            if nv != pre:
                dfs(nv, now)
        

        if old == -1:
            dp.pop()
        else:
            dp[idx] = old

    
    dfs(0, -1)

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

def __starting_point():
    main()
__starting_point()

import sys
input=sys.stdin.readline
sys.setrecursionlimit(100000000)

from bisect import bisect_left,bisect_right
n=int(input())
a=list(map(int,input().split()))
G=[[]for i in range(n)]
for i in range(n-1):
  u,v=map(int,input().split())
  G[u-1].append(v-1)
  G[v-1].append(u-1)

lis=[a[0]]
stack=[]
ans=[1]*n
def dfs(cur,p=-1):
  for nx in G[cur]:
    if nx==p:continue
    idx=bisect_left(lis,a[nx])
    if idx==len(lis):
      stack.append((idx,-1))
      lis.append(a[nx])
    else:
      stack.append((idx,lis[idx]))
      lis[idx]=a[nx]
    
    ans[nx]=len(lis)

    dfs(nx,cur)

    idx,v=stack.pop()
    if v<0:
      lis.pop()
    else:
      lis[idx]=v

dfs(0)
print(*ans,sep="\n")

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
from bisect import bisect_left
INF = float("inf")


from collections import defaultdict


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)

    def add_edge(self, f, t, w=1):
        self.E[f].append((t, w))
        self.E[t].append((f, w))


def solve(N: int, a: "List[int]", u: "List[int]", v: "List[int]"):

    g = Graph(N)
    for x, y in zip(u, v):
        g.add_edge(x-1, y-1)

    ans = [0]*N

    dp = [INF]*N
    event = []
    var = {"last": 0}

    def dfs(curr, par):
        i = bisect_left(dp, a[curr])
        if dp[i] > a[curr]:
            if dp[i] == INF:
                var["last"] = i
            event.append((curr, i, dp[i]))
            dp[i] = a[curr]

        ans[curr] = var["last"]+1

        for child, w in g.E[curr]:
            if child == par:
                continue
            dfs(child, curr)

        c, i, v = event[-1]
        if c == curr:
            dp[i] = v
            if v == INF:
                var["last"] = i-1
            event.pop()

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

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    u = [int()] * (N - 1)  # type: "List[int]"
    v = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, a, u, v)


def __starting_point():
    main()

__starting_point()

from collections import deque
from bisect import bisect_left
import sys
def input():return sys.stdin.readline().strip()

def main():
    N = int(input())
    A = tuple(map(int, input().split()))

    to = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        to[a].append(b)
        to[b].append(a)
    
    # bfs
    INF = 10 ** 18
    dp = [INF] * N
    ans = [0] * N

    def dfs(s):
        stack = deque()
        pop = stack.pop
        push = stack.append

        push((s, -1, None))

        while stack:
            now, pre, old = pop()

            # 復元
            if now == -1:
                dp[pre] = old
                continue
            
            a = A[now]
            idx = bisect_left(dp, a)
            old = dp[idx]
            dp[idx] = a

            ans_idx = bisect_left(dp, INF)
            ans[now] = ans_idx

            # 復元用 頂点
            # (フラグ, 変更したidx, 前の値)
            push((-1, idx, old))
            
            for nv in to[now]:
                if nv != pre:
                    push((nv, now, None))
    
    dfs(0)
    print(*ans, sep="\n")

def __starting_point():
    main()
__starting_point()

# 木によって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')


from bisect import bisect_left

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

start = 1

stack = [1]
par = [-1] * (n + 1)
ans = [0] * (n + 1)
used = [False] * (n + 1)
infi = 10 ** 20
LIS = [infi] * (n + 1)
LIS[0] = -infi
position = [(-1, -1)] * (n + 1)


def hantei(val, L):
    pos = bisect_left(L, val)
    pre = L[pos]
    L[pos] = val
    cnt = bisect_left(L, infi)
    return L, pos, pre, cnt


while stack:
    v = stack[-1]
    if not used[v]:
        LIS, pos, pre, cnt = hantei(A[v], LIS)
        position[v] = (pos, pre)
        ans[v] = cnt - 1
    used[v] = True
    if not graph[v]:
        _ = stack.pop()
        basho, atai = position[v]
        LIS[basho] = atai
        continue
    u = graph[v].pop()
    if u == par[v]:
        continue
    par[u] = v
    stack.append(u)

print(*ans[1:], sep="\n")


from collections import deque
from bisect import bisect_left
import sys
sys.setrecursionlimit(10**7)
n=int(input())
a=list(map(int,input().split()))
edge=[[] for _ in range(n)]
for _ in range(n-1):
    u,v=map(int,input().split())
    u-=1
    v-=1
    edge[u].append(v)
    edge[v].append(u)
stack=deque([])
inf=10**18
lis=[inf]*(n+1)
ans=[0 for _ in range(n)]
visited=[True]*n
#print(edge)
def dfs(s):
    visited[s]=False
    idx=bisect_left(lis,a[s])
    stack.append((idx,lis[idx]))
    lis[idx]=a[s]
    ans[s]=bisect_left(lis,inf)
    for x in edge[s]:
        if visited[x]:
            dfs(x)
    idx,val=stack.pop()
    lis[idx]=val
dfs(0)
#print(lis)
for i in range(n):
    print(ans[i])

from bisect import bisect_left as bl
import sys
sys.setrecursionlimit(10**6)
n=int(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)


from collections import deque
import bisect

N=int(input())
A=list(map(int,input().split()))
ans=[0]*N
Edge=[[] for _ in range(N)]
loute=[str(0)]*N
for i in range(N-1):
    u,v=map(int,input().split())
    Edge[u-1].append(v-1)
    Edge[v-1].append(u-1)
  
tmp=deque(str(0))
CHN=deque()
LIS=[10**18]*N
label=[False]*N
while tmp:
    T0=int(tmp[-1])
    if label[T0]:
        tmp.pop()
        pos,Val=CHN.pop()
        LIS[pos]=Val
        continue

    pos=bisect.bisect_left(LIS,A[T0])
    CHN.append((pos,LIS[pos]))
    LIS[pos]=A[T0]
    ans[T0]=bisect.bisect_left(LIS,10**18)

    if Edge[T0]:
        for i in Edge[T0]:
            if label[i]==False:
                tmp.append(i)
        label[T0]=True
    else:
        label[T0]=True
    
for i in range(N):
    print(ans[i])


import sys
sys.setrecursionlimit(10 ** 7)
from bisect import bisect_left
def resolve():
    def dfs(s, parent):
        a = A[s]
        i = bisect_left(dp, a)
        v = dp[i]
        dp[i] = a
        ans[s] = bisect_left(dp, INF)
        for to in G[s]:
            if to == parent:
                continue
            dfs(to, s)
        # 頂点sでの結果をもとに戻す
        dp[i] = v
        return


    N = int(input())
    A = tuple(map(int, input().split()))
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(lambda x:int(x)-1, input().split())
        G[a].append(b)
        G[b].append(a)

    INF = 10 ** 18
    dp = [INF] * N
    ans = [0] * N

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

def __starting_point():
    resolve()

__starting_point()

# 木によって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')


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')


def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    from collections import deque
    from bisect import bisect_left

    N = int(input())
    a = list(map(int, input().split()))
    tree = [[] for _ in [0]*N]
    for u, v in [map(int, input().split()) for _ in [0]*(N-1)]:
        tree[u-1].append(v-1)
        tree[v-1].append(u-1)
    
    dp = [1001001001] * (N+1)
    dp[0] = -1001001001
    ans = [0] * N
    def dfs(now, p=-1):
        idx = bisect_left(dp, a[now])
        old = dp[idx]
        dp[idx] = a[now]
        ans[now] = idx
        if p != -1 and ans[now] < ans[p]:
            ans[now] = ans[p]
        for child in tree[now]:
            if child == p: continue
            dfs(child, now)
        dp[idx] = old
    dfs(0)

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

main()

import sys
sys.setrecursionlimit(100000000)
from  bisect import bisect_left
input = sys.stdin.readline
INF = 1 << 30

MAXN = 200005
G = [[] for _ in range(MAXN)]
dp = [INF] * MAXN
stack = []
ans = [None] * MAXN
def dfs(v,A,p = -1):
    idx = bisect_left(dp,A[v])
    stack.append((idx,dp[idx]))
    dp[idx] = A[v]
    ans[v] = bisect_left(dp,INF)
    for e in G[v]:
        if e == p:
            continue
        dfs(e,A,v)
    idx,p = stack.pop()
    dp[idx] = p

def main():
    N = int(input())
    A = list(map(int,input().split()))
    for _ in range(N - 1):
        a,b = list(map(int,input().split()))
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)
    dfs(0,A)
    print(('\n'.join(map(str,ans[:N]))))
def __starting_point():
    main()
    

    
    

__starting_point()

import sys
sys.setrecursionlimit(10101000)##?
n=int(input())
*a,=list(map(int, input().split()))
t=[[] for _ in range(n)]
for _ in range(n-1):
    u,v=list(map(int, input().split()))
    u-=1;v-=1
    t[u].append(v);t[v].append(u)
    
INF=10**10
eps=0.1
his=[(-1,-1)]*(n+1)
lis=[INF]*(n+1)
ans = [-1]*n
from bisect import bisect_right,bisect_left
def dfs(v):
    l=bisect_left(lis,a[v])#?
    his[v]=(l,lis[l])
    lis[l]=a[v]
    ans[v]=bisect_left(lis,INF)
    for u in t[v]:
        if ans[u]<0:
            dfs(u)
    ll,pre=his[v]
    lis[ll]=pre
dfs(0)
for ai in ans:print(ai)


import sys
import bisect
import copy
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]
inf = 10**9+1

def dfs(v,prev = -1):
    x = As[v]
    if len(LIS) == 0 or x > LIS[-1]:
        old = inf
        i = len(LIS)
        LIS.append(x)
    else:
        i = bisect.bisect_left(LIS, x)
        old = LIS[i]
        LIS[i] = x

    a = len(LIS)
    ans_array[v] = a
    for u in graph[v]:
        if u == prev:
            continue
        dfs(u,v)
    if old == inf:
        LIS.pop(-1)
    else:
        LIS[i] = old

N = int(input())
As = list(map(int,input().split()))
graph = [[] for _ in range(N)]

for i in range(N-1):
    a,b = list(map(int,input().split()))
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
LIS = []
ans_array = [0] * N
dfs(0)
for i in range(N):
    print((ans_array[i]))


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from bisect import bisect_left
def main(N,a,tr):
  ans=[0]*N
  dp=[float('inf')]*(N+1)
  dp[0]=0
  maxa=max(a)+1
  def dfs(p,v,dp):
    i=bisect_left(dp,a[v])
    tmp=dp[i]
    dp[i]=a[v]
    ans[v]=bisect_left(dp,maxa)-1
    for nv in tr[v]:
      if nv!=p:
        dfs(v,nv,dp)
    dp[i]=tmp
  dfs(-1,0,dp)
  print(*ans,sep='\n')
def __starting_point():
  N=int(input())
  a=list(map(int,input().split()))
  tr=[[] for _ in range(N)]
  for _ in range(N-1):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    tr[u].append(v)
    tr[v].append(u)
  main(N,a,tr)

__starting_point()

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")

import sys
from bisect import bisect_left
sys.setrecursionlimit(10**7)
def input():return sys.stdin.readline().strip()

def main():
    N = int(input())
    A = tuple(map(int, input().split()))

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

    INF = 10 ** 18    
    ans = [0] * N
    dp = [INF] * N
    def dfs(now, pre):
        a = A[now]
        idx = bisect_left(dp, a)

        old = dp[idx]
        dp[idx] = a

        ans_idx = bisect_left(dp, INF)
        ans[now] = ans_idx

        
        for nv in to[now]:
            if nv != pre:
                dfs(nv, now)
        

        dp[idx] = old
    
    dfs(0, -1)

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

def __starting_point():
    main()
__starting_point()

import collections
import bisect
import sys

sys.setrecursionlimit(10 ** 8)

def f(v):
    state[v] = 1
    a=As[v]
    idx = bisect.bisect_left(D,a)
    stack.append( (idx,D[idx]) ) # push
    D[idx] = a
    
    ans[v] = bisect.bisect_left(D,float('inf'))

    for u in V[v]:
        if state[u] == 0:
            f(u)

    # 巻き戻し
    i_pre,d_pre=stack.pop()
    D[i_pre] = d_pre



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

D=[float('inf')]*N
stack=collections.deque([])
ans=[0]*N
state=[0]*N

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

f(0)

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

# 木によって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')


# 木によって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')


import bisect
n = int(input())
*A, = map(int, input().split())
G = [[] for i in range(n)]
for i in range(n - 1):
    x, y = map(int, input().split())
    G[x - 1].append(y - 1)
    G[y - 1].append(x - 1)
inf = 10**10
DP = [inf for i in range(n)]
L = [0 for i in range(n)]
Q = [(-1, 0, None)]
while Q:
    p, x, b = Q.pop()
    if x == -1:
        DP[p] = b
        continue
    i = bisect.bisect_left(DP, A[x])
    Q.append((i, -1, DP[i]))
    DP[i] = A[x]
    L[x] = bisect.bisect_left(DP, inf)
    for y in G[x]:
        if y != p:
            Q.append((x, y, None))
print(*L, sep='\n')


# 木によって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')



import math
import bisect

n = int(input())
alist = [0]+list(map(int,input().split()))
uv_list = []
for i in range(n-1):
    u,v = list(map(int,input().split()))
    if u > v:
        u, v = v, u
    uv_list.append([u,v])

tree = [[] for _ in range(n+1)]
for i in range(n-1):
    uv = uv_list[i]
    tree[uv[0]].append(uv[1])
    tree[uv[1]].append(uv[0])
    

queue = [1]
used = [0]*(n+1)
ans = [0]*(n+1)
dp = []
stack = []
while queue != []:
    cur = queue[-1]

    if used[cur] == 0:
        if cur == 1:
            dp.append(alist[cur])
            stack.append([len(dp)-1,None])
        else:
            if alist[cur] > dp[-1]:
                dp.append(alist[cur])
                stack.append([len(dp)-1,None])
            else:
                offset = bisect.bisect_left(dp,alist[cur])
                stack.append([offset,dp[offset]])
                dp[offset] = alist[cur]
        ans[cur] = len(dp)

    if tree[cur] != [] and used[cur] == 0:
        for child in tree[cur]:
            if used[child] == 0:
                queue.append(child)
    else:
        queue.pop()

        #reverse
        back = stack.pop()
        if back[1] == None:
            dp.pop()
        else:
            dp[back[0]] = back[1]
    used[cur] = 1
for i in range(n):
    print((ans[i+1]))


def main():

    from bisect import bisect_left as bl

    n = int(input())
    a = list(map(int, input().split()))
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    g = [set() for _ in [0]*n]
    ans = [0]*n
    [g[a-1].add(b-1) for a, b in ab]
    [g[b-1].add(a-1) for a, b in ab]
    visited = [False]*n

    q = [0]
    lis = []
    while q:
        i = q.pop()
        ai = a[i]
        if not visited[i]:
            b = bl(lis, ai)
            if b == len(lis):
                visited[i] = "push"
                lis.append(ai)
            else:
                visited[i] = [b, lis[b]]
                lis[b] = ai
            ans[i] = len(lis)
        if not g[i]:
            if visited[i] == "push":
                lis.pop()
            else:
                lis[visited[i][0]] = visited[i][1]
        else:
            q.append(i)
            j = g[i].pop()
            g[j].remove(i)
            q.append(j)
    for i in ans:
        print(i)


main()

import bisect

def dfs(graph, root, A, res, lis):
    stack = [(root,)]
    while stack:
        # print(stack)
        state = stack[-1]
        del stack[-1]
        u = state[0]
        if res[u] == -1:
            a = A[u]
            p = bisect.bisect_left(lis, a)
            if p == len(lis):
                stack.append((u, -1))
                lis.append(a)
            else:
                stack.append((u, p, lis[p]))
                lis[p] = a
            res[u] = len(lis)
            for v in graph[u]:
                if res[v] == -1:
                    stack.append((v,))
        else:
            p = state[1]
            if p >= 0:
                lis[p] = state[2]
            else:
                del lis[-1]

n = int(input())
A = [int(x) for x in input().split()]
graph = [[] for i in range(n)]
for i in range(n - 1):
    u, v = [int(x) - 1 for x in input().split()]
    graph[u].append(v)
    graph[v].append(u)
res = [-1] * n
dfs(graph, 0, A, res, [])
print(*res, sep='\n')

import bisect
n = int(input())
*A, = map(int, input().split())
G = [[] for i in range(n)]
for i in range(n - 1):
    x, y = map(int, input().split())
    G[x - 1].append(y - 1)
    G[y - 1].append(x - 1)
inf = 10**10
DP = [inf for i in range(n)]
L = [0 for i in range(n)]
V = [False for i in range(n)]
Q = [(0, -1)]
while Q:
    x, a = Q.pop()
    if a == -1:
        V[x] = True
        i = bisect.bisect_left(DP, A[x])
        Q.append((i, DP[i]))
        DP[i] = A[x]
        L[x] = bisect.bisect_left(DP, inf)
        for y in G[x]:
            if not V[y]:
                Q.append((y, -1))
    else:
        DP[x] = a
print(*L, sep='\n')


#F
import sys
sys.setrecursionlimit(10**8)
from bisect import bisect_left, bisect_right
N = int(input())
a = list(map(int, input().split()))
lists=[[] for i in range(N)]
for i in range(N-1):
    u, v = map(int, input().split())
    lists[u-1].append(v-1)
    lists[v-1].append(u-1)

def search(v,LIS):
    if len(lists[v])==0:
        return
    for u in lists[v]:
        if check[u] == False:
            check[u] = True
            if a[u] > LIS[-1]:
                LIS.append(a[u])
                ans[u] = len(LIS)
                search(u,LIS)
                LIS.pop()
            else:
                ind = bisect_left(LIS,a[u])
                stack = LIS[ind]
                LIS[ind]=a[u]
                ans[u] = len(LIS)
                search(u,LIS)
                LIS[ind]=stack
    return

ans = [0]*N
check = [False]*N
check[0]=True
LIS = [a[0]]
ans[0]=1
search(0,LIS)
print(*ans, sep="\n")

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

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

G = [[] for i in range(N)]
for i in range(N-1):
    uv = list(map(lambda x: int(x)-1, input().split()))
    G[uv[0]].append(uv[1])
    G[uv[1]].append(uv[0])

dp = [10 ** 10 for _ in range(N+1)]
dp[0] = -1
ans = [-1] * N

def dfs(v, p, max_):
    i = bisect_left(dp, a[v])
    memo = (i, dp[i])
    dp[i] = a[v]

    if i > max_:
        max_ = i
    ans[v] = max_

    for nv in G[v]:
        if nv == p:
            continue
        dfs(nv, v, max_)
    dp[memo[0]] = memo[1]

dfs(0, -1, 0)

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


import sys
sys.setrecursionlimit(2147483647)

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

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

ans=[0]*n
import bisect

#bisect.bisect_left(a, 4) #被ったら左側のindexを返す
#bisect.bisect_right(a, 4)#被ったら右側のindexを返す

def lisOnTree(x,lis):
    nonlocal ans,tree,a,n
    i=bisect.bisect_left(lis, a[x])
    if i==len(lis):
        lis.append(a[x])
        flag="append"
    else:
        flag=(i,lis[i])
        lis[i]=a[x]
    #print(x,lis)
    ans[x]=len(lis)
    for item in tree[x]:
        if ans[item]==0:
            lisOnTree(item,lis)
    if flag=="append":
        lis.pop()
    else:
        lis[flag[0]]=flag[1]

lisOnTree(0,[])

for item in ans:
    print(item)