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
//make sure to make new file!
import java.io.*;
import java.util.*;
//replace treeset with arraylist
public class Main{

   public static int[] values;
   public static ArrayList<ArrayList<Integer>> adj;
   public static ArrayList<ArrayList<Integer>> lis;
   public static int[] answer;
   
   public static void main(String[] args)throws IOException{
      BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
      PrintWriter out = new PrintWriter(System.out);
      
      int n = Integer.parseInt(f.readLine());
      
      StringTokenizer st = new StringTokenizer(f.readLine());
      values = new int[n+1];
      for(int k = 1; k <= n; k++){
         values[k] = Integer.parseInt(st.nextToken());
      }
      
      adj = new ArrayList<ArrayList<Integer>>(n+1);
      for(int k = 0; k <= n; k++) adj.add(new ArrayList<Integer>());
      
      for(int k = 0; k < n-1; k++){
         st = new StringTokenizer(f.readLine());
         int a = Integer.parseInt(st.nextToken());
         int b = Integer.parseInt(st.nextToken());
         
         adj.get(a).add(b);
         adj.get(b).add(a);
      }
      
      
      lis = new ArrayList<ArrayList<Integer>>();
      answer = new int[n+1];
      
      dfs(1, -1);
      
      StringJoiner sj = new StringJoiner("\n");
      for(int k = 1; k <= n; k++){
         sj.add(""+answer[k]);
      }
      out.println(sj.toString());
      
      
      
      out.close();
   }
   
   public static void dfs(int v, int p){
      int loc = -1;
      //get answer for itself
      if(lis.isEmpty()){
         lis.add(new ArrayList<Integer>());
         lis.get(0).add(values[v]);
         loc = 0;
      } else if(values[v] <= lis.get(0).get(lis.get(0).size()-1)){
          //add to first list
         lis.get(0).add(values[v]);
         
         loc = 0;
      } else if(values[v] > lis.get(lis.size()-1).get(lis.get(lis.size()-1).size()-1)){
         //add
         lis.add(new ArrayList<Integer>());
         lis.get(lis.size()-1).add(values[v]);
         loc = lis.size()-1;
      } else {
         int l = 0;
         int r = lis.size()-1;
         int ans = r;
         
         while(l <= r){
            int mid = l + (r-l)/2;
            
            if(values[v] <= lis.get(mid).get(lis.get(mid).size()-1)){
               r = mid-1;
               ans = mid;
            } else {
               l = mid+1;
               
            }
         }
         
         
         lis.get(ans).add(values[v]);
         
         loc = ans;
      }
      
      answer[v] = lis.size();
      
      for(int nei : adj.get(v)){
         if(nei == p) 
            continue;
         dfs(nei,v);
      }
      
      //remove
      lis.get(loc).remove(lis.get(loc).size()-1);
      if(lis.get(loc).isEmpty()){
         lis.remove(lis.size()-1);
      }
      
      
   }
}