AtCoder Beginner Contest 165 - LIS on Tree

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: MEDIUM_HARD

Starter code:

Solutions:
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)
MOD = 1000000007
INF = float('inf')
sys.setrecursionlimit(10 ** 6 + 10)
from bisect import bisect_left

def dfs(i, before):
	nonlocal seq
	nonlocal ans
	added = 0
	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[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, math, copy, queue, itertools, bisect, collections, heapq
sys.setrecursionlimit(10 ** 7)
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
INF = 10 ** 9 + 1
MOD = 10 ** 9 + 7
DD = ((1, 0), (-1, 0), (0, 1), (0, -1))
N = NI()
a = LI()
root = [[] for _ in range(N)]
for _ in range(N - 1):
	(u, v) = LI()
	root[u - 1].append(v - 1)
	root[v - 1].append(u - 1)
lis = [INF for _ in range(N)]
q = []
q.append((0, 0, 0))
ans = [-1 for _ in range(N)]
while q:
	(c, p, v) = q.pop()
	if c == 0:
		x = bisect.bisect_left(lis, a[p])
		y = lis[x]
		if y == INF:
			v += 1
		if y > a[p]:
			lis[x] = a[p]
		ans[p] = v
		q.append((1, x, y))
		for d in root[p]:
			if ans[d] < 0:
				q.append((0, d, v))
	else:
		lis[p] = v
print(*ans, sep='\n')


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 = [100000000000.0 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 = [1e+101 for _ in range(N)]
minimum = [1e+101 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, 1e+51)
	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]


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

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

def get_nums_l():
	return [int(s) for s in input().split(' ')]

def log(*args):
	print('DEBUG:', *args, file=sys.stderr)
INF = 999999999999999999999999
n = int(input())
A = [-INF] + get_nums_l()
edges = [[] for _ in range(n + 1)]
for line in map(lambda s: s.strip(), sys.stdin.readlines()):
	(u, v) = map(int, line.split())
	edges[u].append(v)
	edges[v].append(u)

def dfs(dp, u, p=None):
	i = bisect_left(dp, A[u])
	old = dp[i]
	dp[i] = A[u]
	ans[u] = bisect_left(dp, INF) - 1
	for v in edges[u]:
		if v == p:
			continue
		dfs(dp, v, u)
	dp[i] = old
ans = [0] * (n + 1)
dp = [INF] * (n + 1)
dp[0] = -INF
dfs(dp, 1, None)
for i in range(1, n + 1):
	print(ans[i])


from bisect import bisect_left
from sys import setrecursionlimit
setrecursionlimit(3 * 10 ** 5)
INF = 10 ** 10
N = int(input())
a = list(map(int, input().split()))
T = [set() for x in range(N)]
for i in range(N - 1):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	T[u].add(v)
	T[v].add(u)
search = [0] * N
A = [INF] * N
ans = [-1] * N

def dfs(V):
	num = a[V]
	num = a[V]
	k = bisect_left(A, num)
	v = A[k]
	A[k] = num
	ans[V] = bisect_left(A, INF)
	for VV in T[V]:
		if search[VV]:
			continue
		search[VV] = 1
		dfs(VV)
	A[k] = v
search[0] = 1
dfs(0)
print(*ans, sep='\n')


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

def main():
	N = int(input())
	a = list(map(int, input().split()))
	edge = [[] for _ in range(N)]
	for _ in range(N - 1):
		(x, y) = map(int1, input().split())
		edge[x].append(y)
		edge[y].append(x)
	stack = [(0, 1)]
	used = [False] * N
	ans = [0] * N
	dp = [INF] * (N + 1)
	dp[0] = 0
	dpdp = []
	prev_l = 1

	def dfs(v, l):
		used[v] = True
		index = bisect_right(dp, a[v] - 1, hi=l)
		dpdp = (index, dp[index])
		dp[index] = a[v]
		ans[v] = bisect_left(dp, INF, hi=l + 1) - 1
		for nv in edge[v]:
			if not used[nv]:
				(i, x) = dfs(nv, l + 1)
				dp[i] = x
		return dpdp
	dfs(0, 1)
	for a in ans:
		print(a)
main()


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


import math
import itertools
import queue
import bisect
from collections import deque, defaultdict
import heapq as hpq
from sys import stdin, setrecursionlimit
ipt = stdin.readline
setrecursionlimit(10 ** 7)

def main():
	n = int(ipt())
	a = [int(i) for i in ipt().split()]
	way = [[] for i in range(n)]
	for i in range(n - 1):
		(u, v) = map(int, ipt().split())
		u -= 1
		v -= 1
		way[u].append(v)
		way[v].append(u)
	ans = [0] * n
	dp = [10 ** 18] * n
	stk = []

	def solve(ni, pi):
		ai = a[ni]
		pt = bisect.bisect_left(dp, ai)
		stk.append((pt, dp[pt]))
		dp[pt] = ai
		ans[ni] = bisect.bisect_left(dp, 10 ** 18 - 1)
		for i in way[ni]:
			if i == pi:
				continue
			else:
				solve(i, ni)
		(pl, val) = stk.pop()
		dp[pl] = val
		return None
	solve(0, -1)
	for i in ans:
		print(i)
	return None
main()


import bisect
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
N = int(input())
A = tuple(map(int, input().split()))
graph = [[] for _ in range(N + 1)]
for _ in range(N - 1):
	(x, y) = map(int, input().split())
	graph[x].append(y)
	graph[y].append(x)
ans = [-1] * (N + 1)
inf = 10 ** 18
LIS = [inf] * (N + 1)

def DFS(s, parent=0):
	a = A[s - 1]
	i = bisect.bisect_left(LIS, a)
	v = LIS[i]
	LIS[i] = a
	ans[s] = bisect.bisect_left(LIS, inf)
	for t in graph[s]:
		if t == parent:
			continue
		DFS(t, s)
	LIS[i] = v
	return
DFS(1)
print(*ans[1:], sep='\n')


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
import sys
sys.setrecursionlimit(1000000)

def dfs(p):
	ai = a[p]
	i = bisect_left(dp, ai)
	old = dp[i]
	dp[i] = ai
	ans[p] = bisect_left(dp, INF) - 1
	for child in to[p]:
		if ans[child] is None:
			dfs(child)
	dp[i] = old
n = int(input())
a = [None] + list(map(int, input().split()))
to = [[] for _ in range(n + 1)]
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	to[u].append(v)
	to[v].append(u)
INF = 10 ** 20
dp = [INF] * (n + 1)
dp[0] = -INF
ans = [None] * (n + 1)
dfs(1)
print('\n'.join(list(map(str, ans[1:]))))


import sys
sys.setrecursionlimit(10 ** 7)
from bisect import bisect_left
n = int(input())
a = list(map(int, input().split()))
uv = [list(map(int, input().split())) for _ in range(n - 1)]
INF = 10 ** 10
adj = [[] for _ in range(n)]
for (u, v) in uv:
	u -= 1
	v -= 1
	adj[u].append(v)
	adj[v].append(u)
arrived = [False] * n
ans = [None] * n
ans[0] = 1
dp = [INF] * n

def dfs(u):
	arrived[u] = True
	for v in adj[u]:
		if not arrived[v]:
			idx = bisect_left(dp, a[v])
			tmp = dp[idx]
			dp[idx] = a[v]
			ans[v] = bisect_left(dp, INF - 1)
			dfs(v)
			dp[idx] = tmp
dp[0] = a[0]
dfs(0)
print(*ans, sep='\n')


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

def dfs(now, p):
	a = A[now]
	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
	ans[now] = len(LIS)
	for to in tree[now]:
		if to == p:
			continue
		dfs(to, now)
	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)]
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')


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(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:
		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]


from bisect import bisect_left, bisect_right
import sys
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)))


from bisect import bisect_left
import sys
sys.setrecursionlimit(1000000)

def dfs(j, parent):
	index = bisect_left(dp, a[j - 1])
	old = dp[index]
	dp[index] = a[j - 1]
	ans[j - 1] = bisect_left(dp, INF) - 1
	for child in to[j]:
		if child != parent:
			dfs(child, j)
	dp[index] = old
n = int(input())
a = list(map(int, input().split()))
to = [[] for _ in range(n + 1)]
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	to[u].append(v)
	to[v].append(u)
INF = 10 ** 20
dp = [INF] * (n + 1)
dp[0] = -INF
ans = [None] * n
dfs(1, -1)
print('\n'.join(list(map(str, 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
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
q = [0]
dp = [INF] * N
ans = [0] * N
lis_len = 0
idx = [-1] * N
old = [-1] * N
prev = [-1] * N
ss = 0
from bisect import bisect_left
while q:
	now = q.pop()
	if now >= 0:
		a = A[now]
		idx[now] = bisect_left(dp, a)
		iv = idx[now]
		old[now] = dp[idx[now]]
		x = old[now]
		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(-1 * nxt)
			q.append(nxt)
	else:
		now = -1 * now
		dp[idx[now]] = old[now]
		x = dp[idx[now]]
		if x == INF:
			lis_len -= 1
for a in ans:
	print(a)


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):
		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')
main()


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(*ans, sep='\n')
main()


import bisect
import sys
N = int(input())
a = list(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)
del u, v

def dfs(v):
	if len(dp) == 0 or a[v] > dp[-1]:
		dp.append(a[v])
		pos = -1
	else:
		pos = bisect.bisect_left(dp, a[v])
		back = dp[pos]
		dp[pos] = a[v]
	ans[v] = len(dp)
	for u in to[v]:
		if ans[u] == -1:
			dfs(u)
	if pos == -1:
		dp.pop()
	else:
		dp[pos] = back
ans = [-1] * N
sys.setrecursionlimit(10 ** 6)
dp = []
dfs(0)
for an in ans:
	print(an)


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)

def isok(num, val):
	return num < val

def bisect(ls, val):
	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

def LIS_1(x, ls, 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
	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])
	(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)
for a in ans:
	print(a)


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 bisect
import sys
sys.setrecursionlimit(10 ** 6)
N = int(input())
A = [0] + list(map(int, input().split()))
adj = [[] for n in range(N + 1)]
for n in range(N - 1):
	(u, v) = map(int, input().split())
	adj[u].append(v)
	adj[v].append(u)
ans = [0 for i in range(N + 1)]
INF = 10 ** 10
depth = [-1 for n in range(N + 1)]

def dfs(s, d, lis):
	depth[s] = d
	idx = bisect.bisect_left(lis, A[s])
	(lis[idx], lis_c) = (A[s], lis[idx])
	ans[s] = bisect.bisect_left(lis, INF)
	for i in adj[s]:
		if depth[i] == -1:
			dfs(i, d + 1, lis)
	lis[idx] = lis_c
lis = [INF] * len(A)
dfs(1, 0, lis)
for n in range(1, N + 1):
	print(ans[n])


import sys
input = sys.stdin.readline
from collections import deque
import bisect
n = int(input())
a = list(map(int, input().split()))
links = [[] for _ in range(n + 1)]
for _ in range(n - 1):
	(v, w) = map(int, input().split())
	links[v].append(w)
	links[w].append(v)
inf = 10 ** 10
lis = [inf] * n
inf_ind = 0
parent = [-1] * (n + 1)
operate = [0] * (n + 1)
ans = [-1] * (n + 1)
d = deque()
d.append(1)
while d:
	now = d.popleft()
	if operate[now] == 0:
		p = parent[now]
		if p != -1:
			d.appendleft(now)
		for child in links[now]:
			if child != p:
				parent[child] = now
				d.appendleft(child)
		a_now = a[now - 1]
		ind = bisect.bisect_left(lis, a_now)
		operate[now] = (ind, lis[ind], a_now)
		lis[ind] = a_now
		if inf_ind == ind:
			inf_ind += 1
		ans[now] = inf_ind
	else:
		(ind, before, after) = operate[now]
		lis[ind] = before
		if before == inf:
			inf_ind -= 1
for i in ans[1:]:
	print(i)


import bisect
import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int, input().split()))
edges = [[] for _ in range(n + 1)]
for _ in range(n - 1):
	(from_, to) = map(int, input().split())
	edges[from_].append(to)
	edges[to].append(from_)
DP = [10 ** 9 + 7] * (n + 1)
limit = 10 ** 9 + 1
DP[0] = 0
olds = [None] * (n + 1)
ans = [0] * n
todo = [1]
while todo:
	node = todo.pop()
	if node > 0:
		num = A[node - 1]
		update_idx = bisect.bisect_left(DP, num)
		old = DP[update_idx]
		olds[node] = (old, update_idx)
		DP[update_idx] = num
		lis = bisect.bisect_left(DP, limit) - 1
		ans[node - 1] = lis
		todo.append(-node)
		for to in edges[node]:
			if ans[to - 1]:
				continue
			todo.append(to)
	else:
		node = -node
		(old, update_idx) = olds[node]
		DP[update_idx] = old
for res in ans:
	print(res)


import sys
sys.setrecursionlimit(10 ** 6)
sr = lambda : sys.stdin.readline().rstrip()
ir = lambda : int(sr())
lr = lambda : list(map(int, sr().split()))
from bisect import bisect_left

def resolve():
	N = ir()
	a = lr()
	tr = [[] for _ in range(N)]
	for i in range(N - 1):
		(u, v) = lr()
		tr[u - 1].append(v - 1)
		tr[v - 1].append(u - 1)
	INF = pow(10, 9) + 1
	lis = [INF] * N
	lis[0] = a[0]
	ans = [0] * N
	ans[0] = 1

	def dfs(v, p=-1):
		for u in tr[v]:
			if u == p:
				continue
			idx = bisect_left(lis, a[u])
			prev = lis[idx]
			lis[idx] = a[u]
			ans[u] = bisect_left(lis, INF)
			dfs(u, v)
			lis[idx] = prev
	dfs(0)
	print(*ans, sep='\n')
resolve()


import sys, bisect
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
ans = [1] * n
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)
root = 0
chi = [[] for i in range(n)]
par = [-1] * n
used = [False] * n
tank = [0]
while tank:
	q = tank.pop()
	used[q] = True
	for e in edge[q]:
		if not used[e]:
			chi[q].append(e)
			tank.append(e)
			par[e] = q
tank = [root]
idx = dict()
val = dict()
dp = [10 ** 10] * n
eulerNum = -1
while tank:
	q = tank.pop()
	if q >= 0:
		num = a[q]
		kk = bisect.bisect_left(dp, num)
		val[q] = dp[kk]
		idx[q] = kk
		dp[kk] = num
		ans[q] = bisect.bisect_left(dp, 10 ** 10)
		eulerNum += 1
		tank.append(~q)
		for ch in chi[q]:
			tank.append(ch)
	elif ~q != root:
		if dp[idx[~q]] == a[~q]:
			dp[idx[~q]] = val[~q]
			eulerNum += 1
print(*ans, sep='\n')


import sys
sys.setrecursionlimit(10 ** 6)
from bisect import bisect_left
from collections import deque
n = int(input())
As = list(map(int, input().split()))
edges = [[] for i in range(n)]
for i in range(n - 1):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	edges[u].append(v)
	edges[v].append(u)
INF = 10 ** 10
dp = []
pos = 0
ans = [0] * n
q = deque([])

def dfs(v, p):
	global pos
	a = As[v]
	ind = bisect_left(dp, a)
	if ind == len(dp):
		dp.append(a)
		q.append((True, -1, -1))
	else:
		tmp = dp[ind]
		dp[ind] = a
		q.append((False, ind, tmp))
	ans[v] = len(dp)
	for u in edges[v]:
		if u == p:
			continue
		dfs(u, v)
		(isappend, ind, tmp) = q.pop()
		if isappend:
			dp.pop()
		else:
			dp[ind] = tmp
dfs(0, -1)
print(*ans)


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


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

def main():
	n = int(input())
	A = list(map(int, input().split()))
	Edges = [[] for _ in range(n)]
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		Edges[u].append(v)
		Edges[v].append(u)
	LIS = [10 ** 11] * n
	Ans = [0] * n

	def dfs(v, par):
		idx = bisect_left(LIS, A[v])
		tmp = LIS[idx]
		LIS[idx] = A[v]
		Ans[v] = bisect_left(LIS, 10 ** 10)
		for chi in Edges[v]:
			if chi == par:
				continue
			dfs(chi, v)
		LIS[idx] = tmp
	dfs(0, -1)
	print(*Ans, sep='\n')
main()


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))
	a = [int(next(tokens)) for _ in range(N)]
	u = [int()] * (N - 1)
	v = [int()] * (N - 1)
	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()


import bisect
import sys
sys.setrecursionlimit(10 ** 8)
n = int(input())
A = list(map(int, input().split()))
edges = [[] for _ in range(n)]
for _ in range(n - 1):
	(from_, to) = map(int, input().split())
	edges[from_ - 1].append(to - 1)
	edges[to - 1].append(from_ - 1)
DP = [10 ** 9 + 7] * (n + 1)
DP[0] = 0
ans = [0] * n

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


import sys
from bisect import bisect_left
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 10
changed = []
input = sys.stdin.readline
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 = [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])
	Ans[i] = bisect_left(LIS, INF)
	for nextN in g[i]:
		if nextN != pre:
			dfs(nextN, i, Ans)
	(backID, backV) = changed.pop()
	LIS[backID] = backV
	return 0

def main():
	Ans = [1] * n
	dfs(0, 0, Ans)
	for i in Ans:
		print(i)
	return 0
main()


import sys
import bisect
INF = 1145141919
a = []
dp = []
ans = []
T = []

def dfs(v: int, p: int):
	index = bisect.bisect_left(dp, a[v])
	(dp[index], a[v]) = (a[v], dp[index])
	ans[v] = bisect.bisect_left(dp, INF)
	for u in T[v]:
		if u != p:
			dfs(u, v)
	(dp[index], a[v]) = (a[v], dp[index])

def solve(N: int, tmp_a: 'List[int]', tmp_T: 'List[List[int]]'):
	sys.setrecursionlimit(10 ** 6)
	global dp, ans, a, T
	dp = [INF] * N
	ans = [0] * N
	a = tmp_a
	T = tmp_T
	dfs(0, -1)
	print('\n'.join(map(str, ans)))

def main():

	def iterate_tokens():
		for line in sys.stdin:
			for word in line.split():
				yield word
	tokens = iterate_tokens()
	N = int(next(tokens))
	a = [int(next(tokens)) for _ in range(N)]
	T = [[] for _ in range(N)]
	for i in range(N - 1):
		u = int(next(tokens)) - 1
		v = int(next(tokens)) - 1
		T[u].append(v)
		T[v].append(u)
	solve(N, a, T)
main()


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)
ans = [-1 for _ in range(n)]
ans[0] = 1
dp = [a[0]]
history = []
parents = [-1 for _ in range(n)]
todo = []
for i in uv[0]:
	todo.append(i)
	parents[i] = 0
while True:
	i = todo.pop(-1)
	if dp[-1] < a[i]:
		dp.append(a[i])
		history.append((-1, 0))
	else:
		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)
	for j in uv[i]:
		if ans[j] == -1:
			todo.append(j)
			parents[j] = i
	if len(todo) == 0:
		break
	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 math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop, heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10 ** 9 + 7
inf = float('inf')

def I():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))
n = I()
a = LI()
edges = [[] for _ in range(n)]
for _ in range(n - 1):
	(u, v) = LI()
	edges[u - 1].append(v - 1)
	edges[v - 1].append(u - 1)
dp = [inf] * n
ans = [None] * n
ans[0] = 1
dp[0] = a[0]

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


import sys
sys.setrecursionlimit(10 ** 7)
import sys
input = sys.stdin.readline
n = int(input())
al = list(map(int, input().split()))
from collections import defaultdict
G = defaultdict(list)
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	G[u - 1].append(v - 1)
	G[v - 1].append(u - 1)
from bisect import bisect
ansl = [0 for i in range(n)]
dp = [float('inf') for _ in range(n + 1)]
dp[0] = -1
used = [0 for i in range(n)]
used[0] = 1
stack = []

def dfs(pos):
	idx = bisect(dp, al[pos] - 1)
	stack.append((idx, dp[idx]))
	dp[idx] = min(al[pos], dp[idx])
	ansl[pos] = bisect(dp, 10 ** 18) - 1
	for v in G[pos]:
		if used[v] == 0:
			used[v] = 1
			dfs(v)
			(idx, k) = stack.pop()
			dp[idx] = k
dfs(0)
flag = False
for i in range(n):
	print(ansl[i])


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
import bisect
INF = 10 ** 10
n = int(input())
a = [int(item) for item in 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)
ans = [0] * n
lis = [INF] * n

def dfs(p, v):
	place = bisect.bisect_left(lis, a[v])
	val = lis[place]
	lis[place] = a[v]
	ans[v] = bisect.bisect_left(lis, INF)
	for nv in edge[v]:
		if nv == p:
			continue
		dfs(v, nv)
	lis[place] = val
dfs(-1, 0)
for item in ans:
	print(item)


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


import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.buffer.readline
from bisect import bisect_left
n = int(input())
(*a,) = map(int, input().split())
dp = [float('inf')] * n
con = [[] for _ in range(n)]
for _ in range(n - 1):
	(s, t) = map(int, input().split())
	con[s - 1].append(t - 1)
	con[t - 1].append(s - 1)
ans = [0] * n

def dfs(cur, pre):
	idx = bisect_left(dp, a[cur])
	bef = dp[idx]
	dp[idx] = min(bef, a[cur])
	ans[cur] = bisect_left(dp, float('inf'))
	for nxt in con[cur]:
		if pre != nxt:
			dfs(nxt, cur)
	dp[idx] = bef
dfs(0, -1)
print('\n'.join(map(str, ans)))


import bisect
import sys
sys.setrecursionlimit(202020)
inf = float('inf')
N = int(input())
A = list(map(int, input().split()))
on = [[] for _ in range(N)]
for _ in range(N - 1):
	(u, v) = map(int, input().split())
	on[u - 1].append(v - 1)
	on[v - 1].append(u - 1)
DP = [inf] * (N + 1)
stack = []
ans = [-1] * N
seen = [False] * N

def dfs(gragh, v):
	seen[v] = True
	ind = bisect.bisect_left(DP, A[v])
	mae = DP[ind]
	DP[ind] = A[v]
	stack.append([ind, mae])
	ans[v] = bisect.bisect_left(DP, inf)
	for next_v in gragh[v]:
		if seen[next_v]:
			continue
		dfs(gragh, next_v)
	(ind, mae) = stack.pop()
	DP[ind] = mae
	return
dfs(on, 0)
for a in ans:
	print(a)


import sys
sys.setrecursionlimit(2147483647)
INF = float('inf')
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()
from bisect import bisect_left

def resolve():
	n = int(input())
	A = list(map(int, input().split()))
	E = [[] for _ in range(n)]
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		E[u].append(v)
		E[v].append(u)
	dp = [INF] * (n + 1)
	dp[0] = -INF
	res = 0
	ans = [None] * n
	change = [None] * n
	stack = [(0, -1)]
	while stack:
		(v, p) = stack.pop()
		if v >= 0:
			idx = bisect_left(dp, A[v])
			change[v] = (idx, dp[idx])
			res = max(res, idx)
			ans[v] = res
			dp[idx] = A[v]
			for nv in E[v]:
				if nv == p:
					continue
				stack.append((~nv, v))
				stack.append((nv, v))
		else:
			v = ~v
			(idx, prev) = change[v]
			dp[idx] = prev
			res = ans[p]
	print(*ans)
resolve()


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


from bisect import bisect_left as bisect
import sys
sys.setrecursionlimit(10 ** 9)
N = int(input())
a = list(map(int, input().split()))
g = [[] for _ in range(N)]
for i in range(N - 1):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	g[u].append(v)
	g[v].append(u)
ans = [0] * N

def dfs(t, f, l):
	res = 0
	i = bisect(l, a[t])
	if len(l) == i:
		l.append(a[t])
	else:
		res = [i, l[i]]
		l[i] = a[t]
	ans[t] = len(l)
	for v in g[t]:
		if v != f:
			back = dfs(v, t, l)
			if back:
				l[back[0]] = back[1]
			else:
				l.pop()
	return res
dfs(0, 0, [])
for i in range(N):
	print(ans[i])


import sys
import bisect

def dfs(edge):
	insert = bisect.bisect_left(lis_array, a_array[edge - 1])
	old = lis_array[insert]
	lis_array[insert] = a_array[edge - 1]
	ans = bisect.bisect_left(lis_array, INF)
	ans_array[edge - 1] = ans
	for next_edge in node_dic[edge]:
		if use_array[next_edge - 1] == -1:
			use_array[next_edge - 1] = 1
			dfs(next_edge)
	lis_array[insert] = old
sys.setrecursionlimit(10 ** 9)
N = int(input())
a_array = list(map(int, input().split()))
node_dic = {}
for _ in range(N - 1):
	(u, v) = map(int, input().split())
	if u in node_dic:
		node_dic[u].append(v)
	else:
		node_dic[u] = [v]
	if v in node_dic:
		node_dic[v].append(u)
	else:
		node_dic[v] = [u]
use_array = [-1] * N
ans_array = [0] * N
INF = 2 * 10 ** 9
lis_array = [INF] * N
use_array[0] = 1
dfs(1)
print('\n'.join(map(str, ans_array)))


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

class Tree:
	DUMMY = 0

	def __init__(self, num_node, node_values):
		self.node_values = [-1] + node_values
		self.edges = [None] * (num_node + 1)
		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)

	def node_values(self, node_values):
		self.node_values = [-1] + node_values

	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):
		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])
		for to in self.edges[node_id]:
			if to == prev:
				continue
			self.dps(to, node_id, depth + 1)
		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()


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


n = int(input())
l = [0] + list(map(int, input().split()))
edge = [[] for i in range(n + 1)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	edge[a].append(b)
	edge[b].append(a)
s = 1
ans = [0 for i in range(n + 1)]
from bisect import bisect_left, bisect_right
INF = float('inf')
import sys
sys.setrecursionlimit(10 ** 6)
dep = [-1 for i in range(n + 1)]

def dfs(s, d, c):
	dep[s] = d
	x = bisect_left(c, l[s])
	(c[x], y) = (l[s], c[x])
	ans[s] = bisect_left(c, INF)
	for i in edge[s]:
		if dep[i] == -1:
			dfs(i, d + 1, c)
	c[x] = y
c = [INF] * len(l)
dfs(1, 0, c)
for i in range(1, n + 1):
	print(ans[i])


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

def dfs(v, p, links, state, ans):
	ans[v] = len(state)
	for u in links[v]:
		if u == p:
			continue
		a = aaa[u]
		(b, i) = (-1, -1)
		if state[-1] < a:
			state.append(a)
		else:
			i = bisect_left(state, a)
			b = state[i]
			state[i] = a
		dfs(u, v, links, state, ans)
		if b == -1:
			state.pop()
		else:
			state[i] = b
n = int(input())
aaa = list(map(int, input().split()))
links = [set() for _ in range(n)]
for line in sys.stdin:
	(u, v) = map(int, line.split())
	u -= 1
	v -= 1
	links[u].add(v)
	links[v].add(u)
ans = [0] * n
dfs(0, -1, links, [aaa[0]], ans)
print('\n'.join(map(str, ans)))


def main():
	import sys
	input = sys.stdin.readline
	sys.setrecursionlimit(10 ** 7)
	from collections import Counter, deque
	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
	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)
	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 collections import deque
import bisect
import sys
sys.setrecursionlimit(500000)
n = int(input())
a = list(map(int, input().split()))
to = [list() for _ in range(n)]
for i in range(n - 1):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	to[u].append(v)
	to[v].append(u)
INF = 1001001001
dp = [INF] * n
dp[0] = a[0]
ansls = [0] * n
ansls[0] = 1
history = deque()

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


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


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)


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

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


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
	maxa = max(a) + 1

	def dfs(v, p, dp):
		x = a[v]
		idx = bl(dp, x)
		tmp = dp[idx]
		dp[idx] = x
		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)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(2 * 10 ** 5 + 100)
from bisect import *

def dfs(v, pv):
	j = bisect_left(dp, a[v])
	prev = dp[j]
	dp[j] = a[v]
	ans[v] = bisect_left(dp, 10 ** 18) - 1
	for nv in G[v]:
		if nv == pv:
			continue
		dfs(nv, v)
	dp[j] = prev
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())
	G[u - 1].append(v - 1)
	G[v - 1].append(u - 1)
dp = [10 ** 18] * (N + 1)
dp[0] = -10 ** 18
ans = [-1] * N
dfs(0, -1)
for ans_i in ans:
	print(ans_i)


from bisect import bisect
from sys import setrecursionlimit
setrecursionlimit(10000000)
N = int(input())
A = tuple(map(int, input().split()))
adj = [list() for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	adj[a].append(b)
	adj[b].append(a)
res = [None] * N
dp = [float('inf') for _ in range(N)]

def rec(v, ml):
	a = A[v]
	i = bisect(dp, a - 1)
	ml += int(ml == i)
	res[v] = ml
	orig = dp[i]
	dp[i] = a
	for u in adj[v]:
		if res[u] is None:
			rec(u, ml)
	dp[i] = orig
rec(0, 0)
print(*res, sep='\n')


import sys, math, itertools, collections, bisect
input = lambda : sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf')
mod = 10 ** 9 + 7
mans = inf
ans = 0
count = 0
pro = 1
sys.setrecursionlimit(10 ** 6)
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())
	u -= 1
	v -= 1
	G[u].append(v)
	G[v].append(u)
dp = [inf] * (n + 10)
dp[0] = A[0]
length = 1
fixed = [-1] * (n + 10)
ans = [0] * n

def dfs(node, pre, length):
	if node != 0:
		if dp[length - 1] < A[node]:
			dp[length] = A[node]
			length += 1
			fixed[node] = inf
		else:
			fixed[node] = dp[bisect.bisect_left(dp, A[node])]
			dp[bisect.bisect_left(dp, A[node])] = A[node]
	ans[node] = length
	for v in G[node]:
		if v == pre:
			continue
		dfs(v, node, length)
	dp[bisect.bisect_left(dp, A[node])] = fixed[node]
dfs(0, -1, 1)
print(*ans, sep='\n')

def LIS(seq):
	dp = [inf] * (n + 10)
	dp[0] = seq[0]
	length = 1
	for i in range(1, n):
		if dp[length - 1] < seq[i]:
			dp[length] = seq[i]
			length += 1
		else:
			dp[bisect.bisect_left(dp, seq[i])] = seq[i]
	return (dp, length)


import sys
sys.setrecursionlimit(1000000)

def input():
	return sys.stdin.readline()
n = int(input())
aa = [int(i) for i in input().split()]
e = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b) = [int(i) - 1 for i in input().split()]
	e[a].append(b)
	e[b].append(a)
dp = [10 ** 9] * (n + 10)
dp[0] = 0
ans1 = [0] * n
ans2 = [0] * n

def dfs(i=0, r=-1):
	global dp, ans1, ans2
	mi = 0
	ma = n
	while mi != ma:
		mm = (mi + ma) // 2
		if dp[mm] >= aa[i]:
			ma = mm
		else:
			mi = mm + 1
	be = dp[mi]
	dp[mi] = min(dp[mi], aa[i])
	ans1[i] = mi
	ans2[i] = max(ans1[i], ans2[r])
	for j in e[i]:
		if j == r:
			continue
		dfs(j, i)
	dp[mi] = be
dfs()
print('\n'.join(map(str, ans2)))


from bisect import bisect_left

def main():
	N = int(input())
	A = [int(x) for x in input().split()]
	tree = [list() for _ in range(N)]
	for _ in range(N - 1):
		(u, v) = [int(x) for x in input().split()]
		u -= 1
		v -= 1
		tree[u].append(v)
		tree[v].append(u)
	ans = [1] * N

	def dfs(u, par):
		nonlocal ans
		nonlocal dp
		pos = bisect_left(dp, A[u])
		old = dp[pos]
		dp[pos] = A[u]
		ans[u] = bisect_left(dp, float('inf')) - 1
		for v in tree[u]:
			if v == par:
				continue
			dfs(v, u)
		dp[pos] = old
	dp = [float('inf')] * (N + 1)
	dp[0] = float('-inf')
	dfs(0, -1)
	for i in range(N):
		print(ans[i])
import sys
sys.setrecursionlimit(10 ** 6)
main()


from bisect import bisect_left

def main():
	N = int(input())
	A = list(map(int, input().split()))
	adj = [set() for _ in range(N)]
	for i in range(N - 1):
		(u, v) = 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])
main()


import bisect

def dfs(graph, root, A, res, lis):
	stack = [(root,)]
	while 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')


from collections import deque
from bisect import bisect_left
INF = 10 ** 9 + 1
N = int(input())
A = list(map(int, input().split()))
G = [[] for i in range(N)]
for i in range(N - 1):
	(u, v) = list(map(int, input().split()))
	G[u - 1].append(v - 1)
	G[v - 1].append(u - 1)
LIS = [INF] * N
ans = [0] * N
stack = deque()
stack.append((0, None, None))
while stack:
	(c_node, p_node, old_val) = stack.pop()
	if c_node == -1:
		LIS[p_node] = old_val
		continue
	a = A[c_node]
	idx = bisect_left(LIS, a)
	old_val = LIS[idx]
	LIS[idx] = a
	ans[c_node] = bisect_left(LIS, INF)
	stack.append((-1, idx, old_val))
	for next_node in G[c_node]:
		if next_node != p_node:
			stack.append((next_node, c_node, old_val))
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

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)
for i in range(n):
	print(ans[i])


import bisect
import sys
sys.setrecursionlimit(10 ** 9)
n = int(input())
a = [0] + list(map(int, input().split()))
tree = [[] for _ in range(n + 1)]
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	tree[u].append(v)
	tree[v].append(u)
d = [float('inf')] * (n + 1)
ans = [0] * (n + 1)

def dfs(now, pre):
	i = bisect.bisect_left(d, a[now])
	tmp = d[i]
	d[i] = a[now]
	ans[now] = bisect.bisect_left(d, float('inf'))
	for nxt in tree[now]:
		if nxt == pre:
			continue
		dfs(nxt, now)
	d[i] = tmp
dfs(1, -1)
for i in ans[1:]:
	print(i)


import sys
from copy import copy
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
n = int(input())
a = list(map(int, input().split()))
graph = [[] for _ in range(n)]
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	graph[u].append(v)
	graph[v].append(u)
ans = [0] * n
dp = [INF] * n
dp[0] = a[0]

def dfs(v, v_p):
	ans[v] = bisect_left(dp, INF)
	for v_next in graph[v]:
		if v_next == v_p:
			continue
		idx = bisect_left(dp, a[v_next])
		past = dp[idx]
		dp[idx] = a[v_next]
		dfs(v_next, v)
		dp[idx] = past
dfs(0, -1)
print(*ans, sep='\n')


import sys
from bisect import bisect_left
sys.setrecursionlimit(10 ** 6)
(N, *L) = map(int, open(0).read().split())
A = [0] + L[:N]
dic = [[] for i in range(N + 1)]
INF = 10 ** 20
dp = [INF] * N
ans = [0] * (N + 1)
for (u, v) in zip(*[iter(L[N:])] * 2):
	dic[u].append(v)
	dic[v].append(u)

def dfs(v, p):
	i = bisect_left(dp, A[v])
	old = dp[i]
	dp[i] = A[v]
	ans[v] = bisect_left(dp, INF)
	for u in dic[v]:
		if u == p:
			continue
		dfs(u, v)
	dp[i] = old
dfs(1, -1)
for i in range(1, N + 1):
	print(ans[i])


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
from bisect import bisect_left
from collections import defaultdict
sys.setrecursionlimit(1000000)
n = int(input())
a = [int(i) for i in input().split()]
nbs = [[] for _ in range(n)]
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	nbs[u - 1].append(v - 1)
	nbs[v - 1].append(u - 1)
mlen = defaultdict(int)

def getmlen(cur, p):
	for ch in nbs[cur]:
		if ch == p:
			continue
		if a[ch] > dp[-1]:
			dp.append(a[ch])
			mlen[ch] = len(dp)
			getmlen(ch, cur)
			dp.pop(-1)
		else:
			idx = bisect_left(dp, a[ch])
			ov = dp[idx]
			dp[idx] = a[ch]
			mlen[ch] = len(dp)
			getmlen(ch, cur)
			dp[idx] = ov
dp = []
dp.append(a[0])
mlen[0] = 1
getmlen(0, -1)
for i in range(n):
	print(mlen[i])


from bisect import bisect_left
from collections import deque
N = int(input())
A = list(map(int, input().split()))
X = [list(map(int, input().split())) for _ in range(N - 1)]
graph = [[] for _ in range(N)]
for (u, v) in X:
	graph[u - 1].append(v - 1)
	graph[v - 1].append(u - 1)
INF = float('inf')
dp = [INF] * (N + 1)
dp[0] = -INF
rb = [[] for _ in range(N)]
ans = [0] * N
q = deque([(0, 0)])
while q:
	(u, p) = q.pop()
	if p is None:
		(i, x) = rb[u].pop()
		dp[i] = x
		continue
	i = bisect_left(dp, A[u])
	rb[u].append((i, dp[i]))
	dp[i] = A[u]
	ans[u] = max(i, ans[p])
	q.append((u, None))
	for v in graph[u]:
		if v == p:
			continue
		q.append((v, u))
print(*ans)


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)
print(*result)


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) = 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])))
main()


import sys
from bisect import bisect_left
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.buffer.readline
N = int(input())
(*a,) = map(int, input().split())
w = [[] for _ in range(N)]
INF = 10 ** 18
for _ in range(N - 1):
	(u, v) = map(int, input().split())
	w[u - 1].append(v - 1)
	w[v - 1].append(u - 1)
dp = [INF] * N
ans = [0] * N

def dfs(now, pre):
	idx = bisect_left(dp, a[now])
	before = dp[idx]
	dp[idx] = min(before, a[now])
	ans[now] = bisect_left(dp, INF)
	for nxt in w[now]:
		if pre != nxt:
			dfs(nxt, now)
	dp[idx] = before
dfs(0, -1)
print(*ans, sep='\n')


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


from bisect import bisect_left
INF = 10 ** 12
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())
	g[u - 1].append(v - 1)
	g[v - 1].append(u - 1)
dp = [INF] * n
k = [None] * n
ans = [0] * n
s = [0]
while s:
	p = s.pop()
	if k[p] == None:
		s.append(p)
		idx = bisect_left(dp, a[p])
		k[p] = (idx, dp[idx])
		dp[idx] = a[p]
		ans[p] = bisect_left(dp, INF)
		for node in g[p]:
			if k[node] == None:
				s.append(node)
	else:
		(idx, x) = k[p]
		dp[idx] = x
for x in ans:
	print(x)


import bisect
import sys
sys.setrecursionlimit(500000)

def LIS(lis):
	seq = []
	for c in lis:
		ind = bisect.bisect_left(seq, c)
		if ind == len(seq):
			seq.append(c)
		else:
			seq[ind] = c
	return len(seq)
N = int(input())
a = list(map(int, input().split()))
lis = [[] for i in range(N)]
for i in range(N - 1):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	lis[u].append(v)
	lis[v].append(u)
ans = [None] * N

def dfs(v, p, ln):
	ind = bisect.bisect_left(ln, a[v])
	if ind == len(ln):
		mt = None
		ln.append(a[v])
	else:
		mt = ln[ind]
		ln[ind] = a[v]
	ans[v] = len(ln)
	for nex in lis[v]:
		if nex != p:
			dfs(nex, v, ln)
	if mt == None:
		del ln[-1]
	else:
		ln[ind] = mt
	return
dfs(0, 0, [])
for i in range(N):
	print(ans[i])


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


import sys
import bisect
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
T = [[] for _ in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	T[a - 1].append(b - 1)
	T[b - 1].append(a - 1)
F = [-1 for _ in range(N)]
F[0] = 1
INF = 10 ** 9
dp = [INF for _ in range(N + 1)]
dp[0] = A[0]

def dfs(s):
	for d in T[s]:
		if F[d] == -1:
			t = bisect.bisect_left(dp, A[d])
			p = dp[t]
			dp[t] = A[d]
			F[d] = bisect.bisect_left(dp, INF)
			dfs(d)
			dp[t] = p
dfs(0)
print('\n'.join(map(str, F)))


from bisect import bisect_left
import sys

def main():
	input = sys.stdin.readline
	N = int(input())
	(*A,) = 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)
	INF = 10 ** 10
	tbl = [INF] * N
	stk = [(0, 0)]
	ans = [0] * N
	mx = -1
	while stk:
		(s, a) = stk.pop()
		if s == 0:
			v = a
			i = bisect_left(tbl, A[v])
			mx = max(mx, i)
			ans[v] = mx + 1
			stk.append((1, (i, tbl[i])))
			tbl[i] = A[v]
			for to in G[v]:
				if ans[to] > 0:
					continue
				stk.append((0, to))
		else:
			(idx, val) = a
			tbl[idx] = val
			if val == INF:
				mx = idx - 1
	for a in ans:
		print(a)
main()


def f_lis_on_tree(INF=float('inf')):
	import sys
	sys.setrecursionlimit(10 ** 7)
	import bisect
	N = int(input())
	A = [0] + [int(i) for i in input().split()]
	Edges = [[int(i) for i in input().split()] for j in range(N - 1)]
	graph = [[] for _ in range(N + 1)]
	for (a, b) in Edges:
		graph[a].append(b)
		graph[b].append(a)
	ans = [0] * (N + 1)
	visited = [False] * (N + 1)
	visited[1] = True
	lis = [INF] * (N + 1)
	changes = []

	def dfs(v):
		pos = bisect.bisect_left(lis, A[v])
		changes.append((pos, lis[pos]))
		lis[pos] = A[v]
		ans[v] = bisect.bisect_left(lis, INF)
		for child in graph[v]:
			if not visited[child]:
				visited[child] = True
				dfs(child)
		(pos, val) = changes.pop()
		lis[pos] = val
	dfs(1)
	return ' '.join(map(str, ans[1:]))
print(f_lis_on_tree())


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


import sys
input = sys.stdin.readline
import bisect
sys.setrecursionlimit(10 ** 6)
N = int(input())
A = [0] + list(map(int, input().split()))
E = [[] for i in range(N + 1)]
for i in range(N - 1):
	(x, y) = map(int, input().split())
	E[x].append(y)
	E[y].append(x)
USE = [0] * (N + 1)
USE[1] = 1
ANS = [0] * (N + 1)
DP = []

def dfs(x):
	pos = bisect.bisect_left(DP, A[x])
	if pos < len(DP):
		changepos = pos
		old = DP[pos]
		DP[pos] = A[x]
	else:
		changepos = pos
		old = -1
		DP.append(A[x])
	ANS[x] = len(DP)
	for to in E[x]:
		if USE[to] == 0:
			USE[to] = 1
			dfs(to)
	if old == -1:
		DP.pop()
	else:
		DP[changepos] = old
dfs(1)
print(*ANS[1:])


import sys
from collections import defaultdict as dd
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(input())
a = [0] + list(map(int, input().split()))
e = dd(list)
for _ in range(N - 1):
	(u, v) = map(int, input().split())
	e[u].append(v)
	e[v].append(u)
inf = 10 ** 10
lis = [inf] * (N * 2)
s = [1]
vis = [0] * (N + 1)
euler = []
while len(s):
	x = s.pop()
	if x >= 0:
		vis[x] = 1
		euler.append(x)
		for y in e[x]:
			if vis[y]:
				continue
			s.append(~y)
			s.append(y)
	else:
		euler.append(x)
rollback = []
res = [0] * (N + 1)
for x in euler:
	if x >= 0:
		y = bl(lis, a[x])
		rollback.append((y, lis[y]))
		lis[y] = a[x]
		res[x] = bl(lis, inf)
	else:
		(y, v) = rollback.pop()
		lis[y] = v
for r in res[1:]:
	print(r)


import sys
from bisect import bisect_left
sys.setrecursionlimit(1000000)
n = int(input())
a = [int(i) for i in input().split()]
nbs = [[] for _ in range(n)]
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	nbs[u - 1].append(v - 1)
	nbs[v - 1].append(u - 1)
mlen = [0] * n
dp = [float('inf')] * n

def getmlen(cur, p, ctail):
	for ch in nbs[cur]:
		if ch == p:
			continue
		idx = bisect_left(dp, a[ch])
		ov = dp[idx]
		ntail = max(ctail, idx)
		dp[idx] = a[ch]
		mlen[ch] = ntail + 1
		getmlen(ch, cur, ntail)
		dp[idx] = ov
dp[0] = a[0]
mlen[0] = 1
getmlen(0, -1, 0)
for i in range(n):
	print(mlen[i])


import bisect
import sys
sys.setrecursionlimit(1 << 30)

def dfs(i, LIS):
	if a[i] > LIS[-1]:
		LIS.append(a[i])
		ans[i] = len(LIS)
		for j in edges[i]:
			if parent[i] != j:
				parent[j] = i
				dfs(j, LIS)
		LIS.pop()
	else:
		index = bisect.bisect_left(LIS, a[i])
		x = LIS[index]
		LIS[index] = a[i]
		ans[i] = len(LIS)
		for j in edges[i]:
			if parent[i] != j:
				parent[j] = i
				dfs(j, LIS)
		LIS[index] = x
N = int(input())
a = [0] + list(map(int, input().split()))
edges = [[] for _ in range(N + 1)]
ans = [-1] * (N + 1)
parent = [-1] * (N + 1)
for i in range(N - 1):
	(u, v) = map(int, input().split())
	edges[u].append(v)
	edges[v].append(u)
LIS = [a[1]]
dfs(1, LIS)
for i in ans[1:]:
	print(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) = 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)


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


import sys
from bisect import bisect_left
sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline

def solve():
	INF = 10 ** 18
	N = int(rl())
	A = list(map(int, rl().split()))
	graph = [[] for _ in range(N)]
	for _ in range(N - 1):
		(u, v) = map(lambda x: int(x) - 1, rl().split())
		graph[u].append(v)
		graph[v].append(u)
	ans = [-1] * N
	stack = [0]
	dp = [INF] * (N + 1)
	rewind = [(-1, -1) for _ in range(N)]
	while stack:
		node = stack.pop()
		if 0 <= node:
			idx = bisect_left(dp, A[node])
			rewind[node] = (idx, dp[idx])
			dp[idx] = A[node]
			ans[node] = bisect_left(dp, INF)
			stack.append(~node)
			for child in graph[node]:
				if ans[child] == -1:
					stack.append(child)
		else:
			(idx, val) = rewind[~node]
			dp[idx] = val
	print(*ans, sep='\n')
solve()


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


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)
			que.append((child, node))
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')


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


from collections import defaultdict
from bisect import bisect_left
import sys
sys.setrecursionlimit(10 ** 6)
N = int(input())
A = list(map(int, input().split()))
dp = [float('inf')] * N
tree = defaultdict(list)
for _ in range(N - 1):
	(u, v) = list(map(int, input().split()))
	tree[u - 1].append(v - 1)
	tree[v - 1].append(u - 1)
dp[0] = A[0]
ans = [float('inf')] * N
ans[0] = 1

def backtrack(node, visited, tail_idx):
	flag = any([nx not in visited for nx in tree[node]])
	if not flag:
		return
	for nx in tree[node]:
		if nx in visited:
			continue
		visited.add(nx)
		idx = bisect_left(dp, A[nx])
		prev = dp[idx]
		if tail_idx < idx:
			dp[idx] = A[nx]
			new_tail_idx = idx
			ans[nx] = min(new_tail_idx + 1, ans[nx])
			backtrack(nx, visited, new_tail_idx)
		elif A[nx] < dp[idx]:
			dp[idx] = A[nx]
			ans[nx] = min(tail_idx + 1, ans[nx])
			backtrack(nx, visited, tail_idx)
		else:
			ans[nx] = min(tail_idx + 1, ans[nx])
			backtrack(nx, visited, tail_idx)
		dp[idx] = prev
		visited.remove(nx)
backtrack(node=0, visited={0}, tail_idx=0)
for i in ans:
	print(i)


import bisect
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
n = int(input())
a = list(map(int, input().split()))
edges = [[] for _ in range(n)]
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	edges[u - 1].append(v - 1)
	edges[v - 1].append(u - 1)
inf = 10 ** 10
d = [inf for _ in range(n)]
dp = [inf for _ in range(n)]

def dfs(cur, prev):
	memo = bisect.bisect_left(dp, a[cur])
	memo_v = dp[memo]
	dp[memo] = a[cur]
	d[cur] = bisect.bisect_left(dp, inf)
	for to in edges[cur]:
		if to != prev:
			dfs(to, cur)
	dp[memo] = memo_v
dfs(0, -1)
for i in range(n):
	print(d[i])


def main():
	from bisect import bisect_left
	import sys
	sys.setrecursionlimit(10 ** 7)
	input = sys.stdin.readline
	inf = 1 << 30
	N = int(input())
	(*a,) = map(int, input().split())
	g = tuple((set() for _ in range(N)))
	for _ in range(N - 1):
		(u, v) = (int(x) - 1 for x in input().split())
		g[u].add(v)
		g[v].add(u)
	ans = [0] * N
	lis = [inf] * N

	def dfs(v, p=-1):
		i = bisect_left(lis, a[v])
		prev_at_i = lis[i]
		lis[i] = a[v]
		ans[v] = bisect_left(lis, inf)
		for u in g[v]:
			if p == u:
				continue
			dfs(u, v)
		lis[i] = prev_at_i
	dfs(0)
	print(*ans, sep='\n')
main()


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


import sys
from bisect import bisect_left
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	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 LI1():
	return list(map(int1, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

def main():
	n = II()
	aa = LI()
	to = [[] for _ in range(n)]
	for _ in range(n - 1):
		(u, v) = LI1()
		to[u].append(v)
		to[v].append(u)
	dp = [0]
	ans = [0] * n

	def dfs(u=0, pu=-1):
		a = aa[u]
		i = bisect_left(dp, a)
		end = i == len(dp)
		if end:
			dp.append(a)
		else:
			pre = dp[i]
			dp[i] = a
		ans[u] = len(dp) - 1
		for v in to[u]:
			if v == pu:
				continue
			dfs(v, u)
		if end:
			dp.pop()
		else:
			dp[i] = pre
	dfs()
	print(*ans, sep='\n')
main()


from bisect import bisect_right
from sys import setrecursionlimit
setrecursionlimit(10 ** 8)
n = int(input())
A = list(map(int, input().split()))
gr = []
for i in range(n):
	gr.append([])
for i in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	gr[a].append(b)
	gr[b].append(a)
ans = [0] * n
dp = [10 ** 10 for i in range(1 + n)]
dp[0] = -10 ** 10
kek = 1
used = {0}

def dfs(v):
	global kek
	j = bisect_right(dp, A[v] - 1)
	old = dp[j]
	if dp[j - 1] < A[v] < dp[j]:
		old = dp[j]
		dp[j] = A[v]
		if kek == j:
			for h in range(kek + 1, 1 + n):
				if dp[h] == 10 ** 10:
					kek = h
					break
			if kek == j:
				kek = n + 1
	ans[v] = kek - 1
	for u in gr[v]:
		if u not in used:
			used.add(u)
			dfs(u)
	dp[j] = old
	if kek > j and old == 10 ** 10:
		kek = j
dfs(0)
print(*ans)


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


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

def dfs(v, p=-1):
	a = A[v]
	idx = bisect_left(LIS, a)
	old_val = LIS[idx]
	LIS[idx] = a
	ans[v] = bisect_left(LIS, INF)
	for u in G[v]:
		if u == p:
			continue
		dfs(u, v)
	LIS[idx] = old_val
INF = 10 ** 9 + 1
N = int(input())
A = list(map(int, input().split()))
G = [[] for i in range(N)]
for i in range(N - 1):
	(u, v) = list(map(int, input().split()))
	G[u - 1].append(v - 1)
	G[v - 1].append(u - 1)
LIS = [INF] * N
ans = [0] * N
dfs(0)
print(*ans, sep='\n')


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])
	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
solve()


from bisect import bisect_left

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:
		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()


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


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


import sys
import copy
import bisect
sys.setrecursionlimit(202020)
INF = 10 ** 12
MAX_N = 202020
N = int(input())
a = list(map(int, input().split()))
to = [[] for _ in range(N)]
for i in range(N - 1):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	to[u].append(v)
	to[v].append(u)
dp = [INF for _ in range(MAX_N)]
ans = [0 for _ in range(N)]

def dfs(v, p=-1):
	i = bisect.bisect_left(dp, a[v])
	old = dp[i]
	dp[i] = a[v]
	ans[v] = i
	if p != -1:
		ans[v] = max(ans[v], ans[p])
	for u in to[v]:
		if u == p:
			continue
		dfs(u, v)
	dp[i] = old
dp[0] = -INF
dfs(0)
print(*ans)


from bisect import bisect_left
import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
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)
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)))


from bisect import bisect_left
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
n = int(input())
a = list(map(int, input().split()))
G = [[] for _ in range(n)]
for i in range(n - 1):
	(u, v) = map(lambda z: int(z) - 1, input().split())
	G[u].append(v)
	G[v].append(u)
ans = [0 for i in range(n)]
dp = [10 ** 10 for _ in range(n + 1)]
check = [True for _ in range(n)]

def dfs(now):
	check[now] = False
	ite = bisect_left(dp, a[now])
	tmp = dp[ite]
	dp[ite] = a[now]
	ans[now] = bisect_left(dp, 10 ** 10)
	for to in G[now]:
		if check[to]:
			dfs(to)
	dp[ite] = tmp
dfs(0)
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,) = map(int, input().split())
d = defaultdict(list)
for _ in range(N - 1):
	(u, v) = 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
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
sys.setrecursionlimit(2147483647)
n = int(input())
a = list(map(int, input().split()))
tree = [[] for _ in range(n)]
for _ in range(n - 1):
	(aa, bb) = map(int, input().split())
	tree[aa - 1].append(bb - 1)
	tree[bb - 1].append(aa - 1)
ans = [0] * n
import bisect

def lisOnTree(x, lis):
	global 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]
	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)


N = int(input())
A = list(map(int, input().split()))
e_list = [[] for i in range(N)]
for i in range(N - 1):
	(a, b) = list(map(int, input().split()))
	(a, b) = (a - 1, b - 1)
	e_list[a].append(b)
	e_list[b].append(a)
from collections import deque
vi = 0
INF = float('inf')
Q = deque([vi])
DP = [INF] * (N + 1)
ans = [-1] * N
l = [0]

def bisect(DP, a, l):
	if DP[0] >= a:
		if DP[0] == INF:
			l[0] += 1
		b = DP[0]
		DP[0] = a
		return (0, b)
	ok = 0
	ng = N
	while ng - ok > 1:
		if DP[(ok + ng) // 2] >= a:
			ng = (ok + ng) // 2
		else:
			ok = (ok + ng) // 2
	if DP[ng] == INF:
		l[0] += 1
	b = DP[ng]
	DP[ng] = a
	return (ng, b)
checked_list = [False] * N
checked_list[vi] = True
while len(Q) > 0:
	v = Q.pop()
	if type(v) == type(0):
		Q.append(bisect(DP, A[v], l))
		ans[v] = l[0]
		for v1 in e_list[v]:
			if not checked_list[v1]:
				checked_list[v1] = True
				Q.append(v1)
	else:
		(i, a) = v
		DP[i] = a
		if a == INF:
			l[0] -= 1
print(*ans, sep='\n')


N = int(input())
A = [int(a) for a in input().split()]
X = [[] for i in range(N)]
for i in range(N - 1):
	(x, y) = map(int, input().split())
	(x, y) = (x - 1, y - 1)
	X[x].append(y)
	X[y].append(x)

def EulerTour(n, X, i0):

	def bl(k):
		(l, r) = (-1, n)
		while r - l > 1:
			m = (l + r) // 2
			if L[m][-1] < k:
				l = m
			else:
				r = m
		return l + 1
	inf = 1 << 30
	P = [-1] * n
	Q = [~i0, i0]
	ANS = [0] * n
	L = [[inf] for _ in range(n)]
	I = [0] * n
	while Q:
		i = Q.pop()
		if i < 0:
			i = ~i
			L[I[i]].pop()
			continue
		if i >= 0:
			k = A[i]
			b = bl(k)
			L[b].append(k)
			I[i] = b
			ANS[i] = bl(inf)
		for a in X[i][::-1]:
			if a != P[i]:
				P[a] = i
				for k in range(len(X[a])):
					if X[a][k] == i:
						del X[a][k]
						break
				Q.append(~a)
				Q.append(a)
	return ANS
print('\n'.join(map(str, EulerTour(N, X, 0))))


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

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

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


import bisect as bs
import sys
sys.setrecursionlimit(2 * 10 ** 5 + 1)

def dfs(i, nbr, A, prv, done, history, B, ans):
	j = bs.bisect_left(B, A[i])
	if j < len(B):
		history[i] = (B[j], A[i], j)
		B[j] = A[i]
	else:
		history[i] = (-1, A[i], j)
		B.append(A[i])
	ans[i] = len(B)
	done[i] = 1
	for a in nbr[i]:
		if done[a] == 0:
			dfs(a, nbr, A, prv, done, history, B, ans)
			prv[a] = i
	j = history[i][2]
	if history[i][0] >= 0:
		B[j] = history[i][0]
	else:
		B.pop()
N = int(input())
A = list(map(int, input().split()))
nbr = [[] for _ in range(N)]
for _ in range(N - 1):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	nbr[u].append(v)
	nbr[v].append(u)
prv = [-1 for _ in range(N)]
done = [0 for _ in range(N)]
history = [0 for _ in range(N)]
B = []
ans = [0 for _ in range(N)]
dfs(0, nbr, A, prv, done, history, B, ans)
for i in range(N):
	print(ans[i])


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from bisect import bisect_left
N = int(input())
a = [int(i) for i in input().split()]
vec = [[] for _ in range(N)]
for _ in range(N - 1):
	(u, v) = map(int, input().split())
	vec[u - 1].append(v - 1)
	vec[v - 1].append(u - 1)
lis = [a[0]]
ret = [0] * N

def dfs(cur, pre):
	for nex in vec[cur]:
		if nex == pre:
			continue
		if a[nex] > lis[-1]:
			lis.append(a[nex])
			ret[nex] = len(lis)
			dfs(nex, cur)
			lis.pop()
		else:
			pos = bisect_left(lis, a[nex])
			v = lis[pos]
			lis[pos] = a[nex]
			ret[nex] = len(lis)
			dfs(nex, cur)
			lis[pos] = v
dfs(0, -1)
ret[0] = 1
for i in range(N):
	print(ret[i])


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
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()
graph = [[] for _ in range(N + 1)]
for _ in range(N - 1):
	(a, b) = lr()
	graph[a].append(b)
	graph[b].append(a)
answer = [0] * (N + 1)
INF = 10 ** 10
parent = [-1] * (N + 1)

def dfs(n):
	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)


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 sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from itertools import combinations, permutations
from itertools import accumulate
from math import ceil, sqrt, pi

def LLL(a, ls):
	INF = 10 ** 15
	flag = 0
	prev = 0
	indx = 0
	ls_i = bisect_left(ls, a)
	if a < ls[ls_i]:
		flag = 1
		prev = ls[ls_i]
		indx = ls_i
	ls[ls_i] = min(ls[ls_i], a)
	ls_ii = bisect_left(ls, INF)
	return (ls_ii, ls, flag, prev, indx)
MOD = 10 ** 9 + 7
INF = 10 ** 18
N = int(input())
A = [0] + list(map(int, input().split()))
UV = [list(map(int, input().split())) for _ in range(N - 1)]
graph = [[] for _ in range(N + 1)]
for uv in UV:
	(u, v) = uv
	graph[u].append(v)
	graph[v].append(u)
INF = 10 ** 15
LIS = [INF for i in range(N + 2)]
answer = [0] * (N + 1)

def dfs(prev, n, LIS):
	(answer[n], LIS, flag, prv, indx) = LLL(A[n], LIS)
	for g in graph[n]:
		if g != prev:
			dfs(n, g, LIS)
	if flag:
		LIS[indx] = prv
dfs(-1, 1, LIS)
for a in answer[1:]:
	print(a)


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]
	if ans[par] <= idx:
		ans[now] = idx
	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 bisect
import os
import sys
if os.getenv('LOCAL'):
	sys.stdin = open('_in.txt', 'r')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
IINF = 10 ** 18
MOD = 10 ** 9 + 7
N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))
VU = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]
graph = [[] for _ in range(N)]
for (v, u) in VU:
	v -= 1
	u -= 1
	graph[v].append(u)
	graph[u].append(v)
dp = [INF] * (N + 10)
ans = [0] * N
root = 0

def dfs(v, p):
	i = bisect.bisect_left(dp, A[v])
	prev = dp[i]
	dp[i] = A[v]
	ans[v] = bisect.bisect_left(dp, INF)
	for u in graph[v]:
		if u == p:
			continue
		dfs(u, v)
	dp[i] = prev
dfs(root, None)
print(*ans, sep='\n')


import sys
readline = sys.stdin.readline
read = sys.stdin.read
n = int(input())
a = [int(i) for i in readline().split()]
m = map(int, read().split())
g = [[] for _ in range(n)]
for (i, j) in zip(m, m):
	g[i - 1].append(j - 1)
	g[j - 1].append(i - 1)
INF = 10 ** 9
q = [~0, 0]
dp = [INF] * n
ans = [0] * n
val = 0
idx = [-1] * n
old = [-1] * n
parent = [-1] * n
ss = 0
from bisect import bisect_left
while q:
	v = q.pop()
	if v >= 0:
		iv = idx[v] = bisect_left(dp, a[v])
		x = old[v] = dp[idx[v]]
		if x == INF:
			val += 1
		ans[v] = val
		dp[iv] = a[v]
		for c in g[v]:
			if c != parent[v]:
				parent[c] = v
				q.append(~c)
				q.append(c)
	else:
		v = ~v
		x = dp[idx[v]] = old[v]
		if x == INF:
			val -= 1
print(*ans, sep='\n')


import sys
import bisect
sys.setrecursionlimit(10 ** 9)
INF = 2 ** 30
N = int(input())
A = list(map(int, input().split()))
E = []
for i in range(N):
	E.append([])
for i in range(N - 1):
	(u, v) = list(map(int, input().split()))
	u -= 1
	v -= 1
	E[u].append(v)
	E[v].append(u)
ans = [0] * N
dp = [INF] * N

def dfs(now, par, len):
	ok = bisect.bisect_left(dp, A[now])
	memo = dp[ok]
	dp[ok] = A[now]
	ok1 = bisect.bisect_left(dp, INF)
	ans[now] = ok1
	for to in E[now]:
		if to == par:
			continue
		dfs(to, now, len + 1)
	dp[ok] = memo
dfs(0, -1, 0)
for i in range(N):
	print(ans[i])


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 ** 9)
N = int(input())
A = list(map(int, input().split()))
tree = [[] for i in range(N)]
for i in range(N - 1):
	(u, v) = map(int, input().split())
	tree[u - 1].append(v - 1)
	tree[v - 1].append(u - 1)
ans = [0] * N
ans[0] = 1
INF = 10 ** 10
dp = [INF] * N
dp[0] = A[0]
stack = []

def dfs(node, par):
	global ans
	global dp
	global stack
	children = tree[node]
	for child in children:
		if child == par:
			continue
		num = A[child]
		idx = bisect.bisect_left(dp, num)
		stack.append([idx, dp[idx]])
		dp[idx] = num
		ans[child] = bisect.bisect_left(dp, INF)
		dfs(child, node)
		(idx, num) = stack.pop()
		dp[idx] = num
dfs(0, -1)
print(*ans, 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 bisect
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
tree = [[] for _ in range(n)]
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	tree[u - 1].append(v - 1)
	tree[v - 1].append(u - 1)
ans = [0] * n
visited = [0] * n
visited[0] = 1
l = []

def dfs(i):
	s = a[i]
	pi = -1
	pv = -1
	if len(l) == 0 or s > l[-1]:
		l.append(s)
	else:
		pi = bisect.bisect_left(l, s)
		pv = l[pi]
		l[pi] = s
	ans[i] = len(l)
	for ni in tree[i]:
		if not visited[ni]:
			visited[ni] = 1
			dfs(ni)
	if pi == -1:
		l.pop()
	else:
		l[pi] = pv
dfs(0)
for i in ans:
	print(i)


from bisect import bisect_left
import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
a = list(map(int, input().split()))
g = [[] for _ 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 = [float('inf')] * n
ans = [0] * n

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


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque
from bisect import bisect_left
n = int(readline())
A = list(map(int, readline().split()))
g = [[] * n for i in range(n)]
for i in range(n - 1):
	(u, v) = map(int, readline().split())
	u -= 1
	v -= 1
	g[u].append(v)
	g[v].append(u)
que = deque()
inf = 10 ** 9 + 1
dp = [inf] * n
que.append((0, -1))
chk = [False] * n
chk[0] = True
cnt = 0
ans = [1] * n
while que:
	(now, d) = que.pop()
	if d != -1:
		dp[now] = d
	else:
		ind = bisect_left(dp, A[now])
		que.append((ind, dp[ind]))
		dp[ind] = A[now]
		ans[now] = bisect_left(dp, inf)
		cnt += 1
		for i in g[now]:
			if not chk[i]:
				chk[i] = True
				que.append((i, -1))
	if cnt == n:
		break
print(*ans, sep='\n')


import bisect
import sys
sys.setrecursionlimit(10 ** 6)
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline
INF = 2 ** 62 - 1

def read_int():
	return int(buff_readline())

def read_int_n():
	return list(map(int, buff_readline().split()))

def slv(N, A, UV):
	A.insert(0, -1)
	g = [list() for _ in range(0, N + 1)]
	for (u, v) in UV:
		g[u].append(v)
		g[v].append(u)
	ans = [-1] * (N + 1)
	ans[1] = 1
	dp = [INF] * (N + 1)
	dp[0] = A[1]

	def dfs(u, p):
		for v in g[u]:
			if v == p:
				continue
			i = bisect.bisect_left(dp, A[v])
			b = dp[i]
			dp[i] = A[v]
			ans[v] = bisect.bisect_left(dp, INF)
			dfs(v, u)
			dp[i] = b
	dfs(1, 0)
	for i in range(1, N + 1):
		print(ans[i])

def main():
	N = read_int()
	A = read_int_n()
	UV = [read_int_n() for _ in range(N - 1)]
	slv(N, A, UV)
main()


from bisect import bisect_left
import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
a = list(map(int, input().split()))
G = [[] for _ in range(n)]
for i in range(n - 1):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	G[u].append(v)
	G[v].append(u)
lis = [float('inf')] * n
ans = [0] * n

def dp(v, prev):
	i = bisect_left(lis, a[v])
	tmp = lis[i]
	lis[i] = a[v]
	ans[v] = bisect_left(lis, float('inf'))
	for u in G[v]:
		if u != prev:
			dp(u, v)
	lis[i] = tmp
dp(0, -1)
for l in ans:
	print(l)


from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
import sys
sys.setrecursionlimit(max(1000, 2 * n))
ns = defaultdict(set)
for _ in range(n - 1):
	(u, v) = [int(c) for c in input().split()]
	ns[u - 1].add(v - 1)
	ns[v - 1].add(u - 1)
from bisect import bisect_left
l = [a[0]]
ans = [None] * n

def sub(u, prev, lst, old, ind, ans):
	aa = a[u]
	if len(lst) == 0 or aa > lst[-1]:
		lst.append(aa)
		old = -1
		ind = None
	else:
		ind = bisect_left(lst, aa)
		old = lst[ind]
		lst[ind] = aa
	ans[u] = len(lst)
	for v in ns[u]:
		if prev == v:
			continue
		sub(v, u, lst, old, ind, ans)
	if old == -1:
		lst.pop()
	elif old is not None:
		lst[ind] = old
lst = []
sub(0, -1, lst, None, None, ans)
print('\n'.join(map(str, ans)))


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


from bisect import bisect_left
n = int(input())
a = list(map(int, input().split()))
assert len(a) == n
adj = {u: [] for u 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)
lis = [float('inf')] * n
lislen = [0] * n
backup = [None] * n
stack = [(0, 0)]
while len(stack) > 0:
	(p, u) = stack.pop()
	if p == None:
		(l, x) = backup[u]
		lis[l] = x
	else:
		l = bisect_left(lis, a[u])
		backup[u] = (l, lis[l])
		lis[l] = a[u]
		lislen[u] = bisect_left(lis, float('inf'))
		stack.append((None, u))
		for v in adj[u]:
			if v != p:
				stack.append((u, v))
for u in range(n):
	print(lislen[u])


import sys
input = sys.stdin.readline
import bisect
sys.setrecursionlimit(10 ** 7)
n = int(input())
l = list(map(int, input().split()))
e = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	e[a].append(b)
	e[b].append(a)
ans = [0] * n
ans[0] = 1
dp = [l[0]]

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


import sys
stdin = sys.stdin
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
ns = lambda : stdin.readline().rstrip()
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)


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


import sys
input = sys.stdin.readline
from bisect import bisect_left
INF = 10 ** 17
N = int(input())
A = list(map(int, input().split()))
graph = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	graph[a - 1].append(b - 1)
	graph[b - 1].append(a - 1)
stack = [0]
ans = [-1] * N
dp = [INF] * (N + 1)
to_rev = [(-1, -1) for _ in range(N)]
while stack:
	p = stack.pop()
	if p >= 0:
		ind = bisect_left(dp, A[p])
		to_rev[p] = (ind, dp[ind])
		dp[ind] = A[p]
		ans[p] = bisect_left(dp, INF)
		stack.append(~p)
		for np in graph[p]:
			if ans[np] == -1:
				stack.append(np)
	else:
		p = ~p
		(ind, score) = to_rev[p]
		dp[ind] = score
print(*ans, sep='\n')


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 = 1e+18
	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)
main()


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
input = lambda : sys.stdin.readline().rstrip()
n = int(input())
a = [int(x) for x in input().split()]
g = [[] for _ in range(n)]
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	g[u - 1].append(v - 1)
	g[v - 1].append(u - 1)
from collections import defaultdict
import bisect

def dfs(u):
	ans = [-1] * n
	stack = [u]
	operation = defaultdict(list)
	used = [False] * n
	dp = [float('inf')] * n
	dp[0] = a[u]
	used[u] = False
	length = 1
	operation[0] = [0, float('inf'), 0]
	ans[0] = 1
	while stack:
		u = stack[-1]
		if used[u] == False:
			used[u] = True
			idx = bisect.bisect_left(dp, a[u])
			operation[u] = [idx, dp[idx], length]
			dp[idx] = a[u]
			length = max(length, idx + 1)
			ans[u] = length
			for i in g[u]:
				if ans[i] > 0:
					continue
				stack.append(i)
		else:
			(idx, value, length) = operation[u]
			dp[idx] = value
			stack.pop()
	return (ans, used, dp)
(ans, used, dp) = dfs(0)
print(*ans, sep='\n')


import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
from collections import defaultdict
import bisect
INF = float('inf')

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

class Graph(object):

	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

	def get_nodes(self):
		return self.graph.keys()

def Euler_tour(G, node, visit, DP, prev, ans, A):
	for i in G.graph[node]:
		if visit[i] != 'Yes':
			visit[i] = 'Yes'
			x = bisect.bisect_left(DP, A[i])
			prev.append([x, DP[x]])
			DP[x] = A[i]
			ans[i] = bisect.bisect_left(DP, INF)
			Euler_tour(G, i, visit, DP, prev, ans, A)
	(x, val) = prev.pop()
	DP[x] = val

def main():
	N = int(input())
	A = getlist()
	G = Graph()
	for i in range(N - 1):
		(a, b) = getlist()
		a -= 1
		b -= 1
		G.add_edge(a, b)
		G.add_edge(b, a)
	DP = [INF] * N
	DP[0] = A[0]
	prev = [[0, A[0]]]
	ans = [None] * N
	ans[0] = 1
	visit = ['No'] * N
	visit[0] = 'Yes'
	Euler_tour(G, 0, visit, DP, prev, ans, A)
	for i in range(N):
		print(ans[i])
main()


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
input = sys.stdin.readline
n = int(input())
A = [0] + list(map(int, input().split()))
C = [list(map(int, input().split())) for i in range(n - 1)]
sys.setrecursionlimit(10 ** 5 + 5)
M = [[] for i in range(n + 1)]
for i in range(n - 1):
	M[C[i][0]].append(C[i][1])
	M[C[i][1]].append(C[i][0])
V = [0] * (n + 1)
ANS = [0] * (n + 1)
R = [10 ** 10] * (n + 5)
import bisect
R[0] = A[1]
ANS[1] = 1

def des(x):
	V[x] = 1
	for i in M[x]:
		if V[i] == 0:
			V[i] = 1
			ind = bisect.bisect_left(R, A[i])
			ma = R[ind]
			R[ind] = A[i]
			ANS[i] = bisect.bisect_left(R, 10 ** 10 - 1)
			des(i)
			R[ind] = ma
des(1)
for i in range(1, len(ANS)):
	print(ANS[i])


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])
		elif 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()
		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])


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
sysread = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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 = []
	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):
	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 ** 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')


import sys
import time
readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():
	n = int(input())
	a = list(map(int, readline().split()))
	node = {i: [] for i in range(n)}
	for _ in range(n - 1):
		(u, v) = map(int, readline().split())
		(u, v) = (u - 1, v - 1)
		node[u].append(v)
		node[v].append(u)
	ans = [0] * n
	dp = [INF] * n
	dp[0] = a[0]
	visited = [False] * n
	from collections import deque
	import bisect

	def dfs(cur):
		visited[cur] = True
		nv = a[cur]
		index = bisect.bisect_left(dp, nv)
		pv = dp[index]
		dp[index] = nv
		suc = node[cur]
		for nx in suc:
			if not visited[nx]:
				dfs(nx)
		ans[cur] = bisect.bisect_left(dp, INF)
		dp[index] = pv
	dfs(0)
	print(*ans, sep='\n')
main()


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 = []
stack = deque([])

def LISonTree(num, pre):
	p = bisect_left(dp, a[num])
	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
	for x in graph[num]:
		if x == pre:
			continue
		LISonTree(x, num)
	(changed_p, changed_v) = stack.popleft()
	dp[changed_p] = changed_v
LISonTree(0, -1)
for y in ans:
	print(y)


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
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])
		if ci not in v:
			if len(clis) == 0:
				clis.append(A[ci - 1])
				memo[ci].append(-1)
			elif 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()


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
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
n = int(input())
A = list(map(int, input().split()))
edges = [[] for _ in range(n)]
for _ in range(n - 1):
	(u, v) = list(map(lambda x: int(x) - 1, input().split()))
	edges[u].append(v)
	edges[v].append(u)
INF = 10 ** 18
ans = [INF] * n

def dfs(v, parent):
	x = bisect.bisect_left(lis, A[v])
	prev = lis[x]
	lis[x] = A[v]
	ans[v] = bisect.bisect_left(lis, INF)
	for v2 in edges[v]:
		if v2 == parent:
			continue
		dfs(v2, v)
	lis[x] = prev
lis = [INF] * n
dfs(0, -1)
for x in ans:
	print(x)


import bisect
import sys
sys.setrecursionlimit(10 ** 9)
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())
	Edge[u - 1].append(v - 1)
	Edge[v - 1].append(u - 1)
visited = [False] * N
visited[0] = True
answer = [1] * N

def dfs(v, dp):
	for nv in Edge[v]:
		if visited[nv]:
			continue
		visited[nv] = True
		if len(dp) == 0 or A[nv] > dp[-1]:
			dp.append(A[nv])
			answer[nv] = len(dp)
			dfs(nv, dp)
			dp.pop()
		else:
			idx = bisect.bisect_left(dp, A[nv])
			temp = dp[idx]
			dp[idx] = A[nv]
			answer[nv] = len(dp)
			dfs(nv, dp)
			dp[idx] = temp
	return
dfs(0, [A[0]])
answer[0] = 1
for a in answer:
	print(a)


import sys
sys.setrecursionlimit(10 ** 6)
import numpy as np
INF = 10 ** 10
N = int(input())
A = list(map(int, input().split()))
uv = [list(map(int, input().split())) for _ in range(N - 1)]
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):
	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()


n = int(input())
A = list(map(int, input().split()))
peer = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	peer[a].append(b)
	peer[b].append(a)
inf = 10 ** 12
minf = 10 ** 11
pre = [inf for _ in range(n)]
pst = [[] for _ in range(n)]
right = [inf for _ in range(n)]
seen = [0 for _ in range(n)]
seen[0] = 1
now = [0]
while now:
	last = now
	now = []
	for x in last:
		for y in peer[x]:
			if seen[y] == 0:
				now.append(y)
				seen[y] = 1
				pre[y] = x
				right[y] = x
				if pst[x]:
					right[pst[x][-1]] = y
				pst[x].append(y)
down = [i for i in range(n)]
for i in range(n):
	if pst[i]:
		down[i] = pst[i][0]
seen = [0 for _ in range(n)]
import bisect
lis = [inf for _ in range(n)]
rec = [[] for _ in range(n)]
now = 0
ans = [0 for _ in range(n)]
while True:
	if seen[now] == 0:
		seen[now] += 1
		b = bisect.bisect_left(lis, A[now])
		rec[now] = [b, lis[b]]
		lis[b] = A[now]
		ans[now] = bisect.bisect_left(lis, minf)
		now = down[now]
	else:
		seen[now] += 1
		(b, c) = rec[now]
		lis[b] = c
		if now == 0:
			break
		now = right[now]
for x in ans:
	print(x)


from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque, Counter
from operator import mul
import copy
import heapq
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
import bisect
N = int(input())
a = [0] + list(map(int, input().split()))
al = [[] for i in range(N + 1)]
for i in range(N - 1):
	(c, d) = list(map(int, input().split()))
	al[c].append(d)
	al[d].append(c)
visited = [0 for i in range(N + 1)]
LIS = [a[1]]
ans = [0 for i in range(N + 1)]
ans[1] = 1

def dfs_rec(u):
	x = a[u]
	if x > LIS[-1]:
		pre_idx = len(LIS)
		pre_v = INF
		LIS.append(x)
	else:
		pre_idx = bisect.bisect_left(LIS, x)
		pre_v = LIS[pre_idx]
		LIS[bisect.bisect_left(LIS, x)] = x
	ans[u] = len(LIS)
	visited[u] = 1
	for v in al[u]:
		if visited[v] == 0:
			dfs_rec(v)
	if pre_v == INF:
		LIS.pop()
	else:
		LIS[pre_idx] = pre_v
dfs_rec(1)
for i in range(1, N + 1):
	print(ans[i])


from bisect import bisect_left
import sys

def main():
	input = sys.stdin.readline
	N = int(input())
	(*A,) = 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)
	INF = 10 ** 10
	ans = [0] * N
	l = [INF] * (N + 1)
	stk = [(0, 0, 0)]
	while stk:
		(s, a, b) = stk.pop()
		if s == 0:
			i = bisect_left(l, A[a])
			stk.append((1, i, l[i]))
			l[i] = A[a]
			ans[a] = bisect_left(l, INF)
			for to in G[a]:
				if ans[to] > 0:
					continue
				stk.append((0, to, 0))
		else:
			l[a] = b
	for a in ans:
		print(a)
main()


import bisect, sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
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)
dp = [10 ** 20 for i in range(N)]
ans = [-1 for i in range(0, N)]

def dfs(v, pv):
	pos = bisect.bisect_left(dp, a[v])
	prev = dp[pos]
	dp[pos] = a[v]
	ans[v] = bisect.bisect_left(dp, 10 ** 18)
	for i in edge[v]:
		if i == pv:
			continue
		dfs(i, v)
	dp[pos] = prev
dfs(0, -1)
for i in range(N):
	print(ans[i])