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.

Example

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


Output

1
2
3
3
4
4
5
2
2
3
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])


# 0-indexedの場合
V = [0] * (n+1)
# D = [-1] * (n+1)  # 自分を含む、子孫のノード数
ANS = [0] * (n+1)

R = [10**10] * (n+5)

import bisect

R[0] = A[1]
ANS[1] = 1

def des(x):
    # end = 1
    V[x] = 1
    # print(R[:10])


    for i in M[x]:
        if V[i] == 0:
            # print(i)
            # end = 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

    # if end == 1:
    #     print(R)
    #     ANS[x] = bisect.bisect_right(R, 10**10-1)

des(1)

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