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
/*
If you want to aim high, aim high
Don't let that studying and grades consume you
Just live life young
******************************
If I'm the sun, you're the moon
Because when I go up, you go down
*******************************
I'm working for the day I will surpass you
https://www.a2oj.com/Ladder16.html
*/
import java.util.*;
import java.io.*;
import java.math.*;

   public class Main
   {
      public static void main(String omkar[]) throws Exception
      {
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));  
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int N = Integer.parseInt(st.nextToken());
         LinkedList<Integer>[] edges = new LinkedList[N+1];
         for(int i=1; i <= N; i++)
            edges[i] = new LinkedList<Integer>();
         arr = new int[N+1];
         st = new StringTokenizer(infile.readLine());
         for(int i=0; i < N; i++)
            arr[i+1] = Integer.parseInt(st.nextToken());
         compress(arr);
         for(int i=2; i <= N; i++)
         {
            st = new StringTokenizer(infile.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            edges[a].add(b);
            edges[b].add(a);
         }
         dp = new SegmentTree(0, 200002);
         res = new int[N+1];
         dfs(1, edges, 0);
         StringBuilder sb = new StringBuilder();
         for(int i=1; i <= N; i++)
            sb.append(res[i]+"\n");
         System.out.print(sb);
      }
      static int[] arr;
      static SegmentTree dp;
      static int[] res;
      public static void dfs(int curr, LinkedList<Integer>[] edges, int par)
      {
         int val = dp.query(0, arr[curr]-1)+1;
         int past = dp.query(arr[curr], arr[curr]);
         dp.update(arr[curr], Math.max(val, past));
         res[curr] = Math.max(res[curr], Math.max(val, dp.query(0, 200000)));
         for(int next: edges[curr])
            if(next != par)
               dfs(next, edges, curr);
         dp.update(arr[curr], past);
      }
      public static void compress(int[] arr)
      {
         ArrayList<Integer> ls = new ArrayList<Integer>();
         for(int x: arr)
            ls.add(x);
         Collections.sort(ls);
         HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
         int boof = 1;
         for(int x: ls)
            if(!map.containsKey(x))
               map.put(x, boof++);
         for(int i=0; i < arr.length; i++)
            arr[i] = map.get(arr[i]);
      }
   }
   class SegmentTree 
   {
        //range max query, non lazy
        final int[] val;
        final int treeFrom;
        final int length;
    
        public SegmentTree(int treeFrom, int treeTo) 
        {
            this.treeFrom = treeFrom;
            int length = treeTo - treeFrom + 1;
            int l;
            for (l = 0; (1 << l) < length; l++);
            val = new int[1 << (l + 1)];
            this.length = 1 << l;
        }
        public void update(int index, int delta) 
        {
            int node = index - treeFrom + length;
            val[node] = delta;
            for (node >>= 1; node > 0; node >>= 1) 
                val[node] = Math.max(val[node << 1], val[(node << 1) + 1]);
        }
        public int query(int from, int to) 
        {
            if (to < from)
                return 0;
            from += length - treeFrom;
            to += length - treeFrom + 1;
            int res = 0;
            for (; from + (from & -from) <= to; from += from & -from) 
                res = Math.max(res, val[from / (from & -from)]);
            for (; to - (to & -to) >= from; to -= to & -to)
                res = Math.max(res, val[(to - (to & -to)) / (to & -to)]);
            return res;
        }
   }