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 java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
	static class Node{
		List<Integer> adj;
		int val;
		public Node(int v) {
			adj = new ArrayList<Integer>();
			val = v;
		}
	}
	static int bsearch(int[] dp , int len, int val){
		if(len == 0){
			return 0;
		}
		if(dp[len - 1] < val){
			return len;
		}
		if(dp[0] >= val){
			return 0;
		}
		// dp[0] < val
		// dp[len - 1] >= val
		int left = 0;
		int right = len - 1;
		while(right - left > 1){
			int mid = (left + right) / 2;
			if(dp[mid] >= val){
				right = mid;
			}else{
				left = mid;
			}
		}
		return right;
	}
	static void rec(int cur , int parent , int depth , int dpLength , int dp[], int[] result, Node[] ns){
		// update LIS
		int pos = bsearch(dp, dpLength, ns[cur].val);
		int prev = -1;
//		System.out.println(cur+" "+Arrays.toString(dp)+ " "+dpLength);
		if(dpLength <= pos){
			dp[dpLength] = ns[cur].val;
			dpLength += 1;
		}else{
			prev = dp[pos];
			dp[pos] = ns[cur].val;
		}
//		System.out.println(cur+" "+Arrays.toString(dp)+ " "+dpLength);
		result[cur] = dpLength;
		for(int a : ns[cur].adj){
			if(a == parent){
				continue;
			}
			rec(a , cur , depth + 1 , dpLength, dp , result , ns);
		}
		// recover LIS
		if(depth <= pos){
			dpLength--;
		}else{
			dp[pos] = prev;
		}
	}
	public static void main(String[] args) throws Exception{
		Scanner sc = new Scanner(System.in);
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = br.readLine();
		int N = Integer.parseInt(line);
		Node ns[] = new Node[N];
		line = br.readLine();
		String as[] = line.split(" ");
		for(int i = 0 ; i < N ; ++i){
			int a = Integer.parseInt(as[i]);
			ns[i] = new Node(a);
		}
		for(int i = 0 ; i < N - 1; ++i){
			line = br.readLine();
			as = line.split(" ");
			int u = Integer.parseInt(as[0]) - 1;
			int v = Integer.parseInt(as[1]) - 1;
			ns[u].adj.add(v);
			ns[v].adj.add(u);
		}
		int dp[] = new int[N];	
		int result[] = new int[N];
		rec(0 , 0 , 0 , 0 , dp , result , ns);
		StringBuilder sb = new StringBuilder();
		for(int r : result){
			sb.append(r);
			sb.append('\n');
//			System.out.println(r);
		}
		System.out.println(sb);
	}
}
