Although Inzane successfully found his beloved bone, Zane, his owner, has yet to return. To search for Zane, he would need a lot of money, of which he sadly has none. To deal with the problem, he has decided to hack the banks.

<image>

There are n banks, numbered from 1 to n. There are also n - 1 wires connecting the banks. All banks are initially online. Each bank also has its initial strength: bank i has initial strength ai.

Let us define some keywords before we proceed. Bank i and bank j are neighboring if and only if there exists a wire directly connecting them. Bank i and bank j are semi-neighboring if and only if there exists an online bank k such that bank i and bank k are neighboring and bank k and bank j are neighboring.

When a bank is hacked, it becomes offline (and no longer online), and other banks that are neighboring or semi-neighboring to it have their strengths increased by 1.

To start his plan, Inzane will choose a bank to hack first. Indeed, the strength of such bank must not exceed the strength of his computer. After this, he will repeatedly choose some bank to hack next until all the banks are hacked, but he can continue to hack bank x if and only if all these conditions are met:

  1. Bank x is online. That is, bank x is not hacked yet. 
  2. Bank x is neighboring to some offline bank. 
  3. The strength of bank x is less than or equal to the strength of Inzane's computer. 



Determine the minimum strength of the computer Inzane needs to hack all the banks.

Input

The first line contains one integer n (1 ≤ n ≤ 3·105) — the total number of banks.

The second line contains n integers a1, a2, ..., an ( - 109 ≤ ai ≤ 109) — the strengths of the banks.

Each of the next n - 1 lines contains two integers ui and vi (1 ≤ ui, vi ≤ n, ui ≠ vi) — meaning that there is a wire directly connecting banks ui and vi.

It is guaranteed that the wires connect the banks in such a way that Inzane can somehow hack all the banks using a computer with appropriate strength.

Output

Print one integer — the minimum strength of the computer Inzane needs to accomplish the goal.

Examples

Input

5
1 2 3 4 5
1 2
2 3
3 4
4 5


Output

5

Input

7
38 -29 87 93 39 28 -55
1 2
2 5
3 2
2 4
1 7
7 6


Output

93

Input

5
1 2 7 6 7
1 5
5 3
3 4
2 4


Output

8

Note

In the first sample, Inzane can hack all banks using a computer with strength 5. Here is how:

  * Initially, strengths of the banks are [1, 2, 3, 4, 5]. 
  * He hacks bank 5, then strengths of the banks become [1, 2, 4, 5, - ]. 
  * He hacks bank 4, then strengths of the banks become [1, 3, 5, - , - ]. 
  * He hacks bank 3, then strengths of the banks become [2, 4, - , - , - ]. 
  * He hacks bank 2, then strengths of the banks become [3, - , - , - , - ]. 
  * He completes his goal by hacking bank 1. 



In the second sample, Inzane can hack banks 4, 2, 3, 1, 5, 7, and 6, in this order. This way, he can hack all banks using a computer with strength 93.
import java.util.*;
import java.io.*;
public class helloworld {
 static long fact[];
 static long max;
 static int ans;
	static class Reader 
    { 
        final private int BUFFER_SIZE = 1 << 16; 
        private DataInputStream din; 
        private byte[] buffer; 
        private int bufferPointer, bytesRead; 
  
        public Reader() 
        { 
            din = new DataInputStream(System.in); 
            buffer = new byte[BUFFER_SIZE]; 
            bufferPointer = bytesRead = 0; 
        } 
  
        public Reader(String file_name) throws IOException 
        { 
            din = new DataInputStream(new FileInputStream(file_name)); 
            buffer = new byte[BUFFER_SIZE]; 
            bufferPointer = bytesRead = 0; 
        } 
  
        public String readLine() throws IOException 
        { 
            byte[] buf = new byte[64]; // line length 
            int cnt = 0, c; 
            while ((c = read()) != -1) 
            { 
                if (c == '\n') 
                    break; 
                buf[cnt++] = (byte) c; 
            } 
            return new String(buf, 0, cnt); 
        } 
  
        public int nextInt() throws IOException 
        { 
            int ret = 0; 
            byte c = read(); 
            while (c <= ' ') 
                c = read(); 
            boolean neg = (c == '-'); 
            if (neg) 
                c = read(); 
            do
            { 
                ret = ret * 10 + c - '0'; 
            }  while ((c = read()) >= '0' && c <= '9'); 
  
            if (neg) 
                return -ret; 
            return ret; 
        } 
  
        public long nextLong() throws IOException 
        { 
            long ret = 0; 
            byte c = read(); 
            while (c <= ' ') 
                c = read(); 
            boolean neg = (c == '-'); 
            if (neg) 
                c = read(); 
            do { 
                ret = ret * 10 + c - '0'; 
            } 
            while ((c = read()) >= '0' && c <= '9'); 
            if (neg) 
                return -ret; 
            return ret; 
        } 
  
        public double nextDouble() throws IOException 
        { 
            double ret = 0, div = 1; 
            byte c = read(); 
            while (c <= ' ') 
                c = read(); 
            boolean neg = (c == '-'); 
            if (neg) 
                c = read(); 
  
            do { 
                ret = ret * 10 + c - '0'; 
            } 
            while ((c = read()) >= '0' && c <= '9'); 
  
            if (c == '.') 
            { 
                while ((c = read()) >= '0' && c <= '9') 
                { 
                    ret += (c - '0') / (div *= 10); 
                } 
            } 
  
            if (neg) 
                return -ret; 
            return ret; 
        } 
  
        private void fillBuffer() throws IOException 
        { 
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE); 
            if (bytesRead == -1) 
                buffer[0] = -1; 
        } 
  
        private byte read() throws IOException 
        { 
            if (bufferPointer == bytesRead) 
                fillBuffer(); 
            return buffer[bufferPointer++]; 
        } 
  
        public void close() throws IOException 
        { 
            if (din == null) 
                return; 
            din.close(); 
        } 
    } 
	
	static int getSum(int index , int BITree[]) 
    { 
		index++;
        int  sum = 0; // Iniialize result 
      
        // index in BITree[] is 1 more than 
        // the index in arr[] 
    
      
        // Traverse ancestors of BITree[index] 
        while(index>0) 
        { 
            // Add current element of BITree  
            // to sum 
            sum += BITree[index]; 
      
            // Move index to parent node in  
            // getSum View 
            index -= index & (-index); 
        } 
        return sum; 
    } 
  
	static int getMid(int s, int e) 
    { 
        return s + (e - s) / 2; 
    } 
  
    /* 
    * A recursive function to get the sum  
    of values in given range of the array. 
    * The following are parameters for this function. 
    *  
    * st -> Pointer to segment tree 
    * node -> Index of current node in 
    *         the segment tree. 
    * ss & se -> Starting and ending indexes 
    *         of the segment represented 
    *         by current node, i.e., st[node] 
    * l & r -> Starting and ending indexes 
    *         of range query 
    */
    static int MaxUtil(int[] st, int ss, int se,  
                        int l, int r, int node)  
    { 
          
        // If segment of this node is completely 
        // part of given range, then return 
        // the max of segment 
        if (l <= ss && r >= se) 
            return st[node]; 
  
        // If segment of this node does not 
        // belong to given range 
        if (se < l || ss > r) 
            return -1; 
  
        // If segment of this node is partially 
        // the part of given range 
        int mid = getMid(ss, se); 
  
        return Math.max(MaxUtil(st, ss, mid, l, r, 2 * node + 1), 
                    MaxUtil(st, mid + 1, se, l, r, 2 * node + 2)); 
    } 
  
    /* 
    * A recursive function to update the  
    nodes which have the given index in their 
    * range. The following are parameters  
    st, ss and se are same as defined above 
    * index -> index of the element to be updated. 
    */
    static void updateValue(int arr[], int[] st, int ss, 
                    int se, int index, int value, int node) 
    { 
        if (index < ss || index > se) 
        { 
            System.out.println("Invalid Input"); 
            return; 
        } 
  
        if (ss == se) 
        { 
  
            // update value in array and in segment tree 
            arr[index] = value; 
            st[node] = value; 
        }  
        else
        { 
            int mid = getMid(ss, se); 
  
            if (index >= ss && index <= mid) 
                updateValue(arr, st, ss, mid, index, value, 2 * node + 1); 
            else
                updateValue(arr, st, mid + 1, se, index, value, 2 * node + 2); 
  
            st[node] = Math.max(st[2 * node + 1], st[2 * node + 2]); 
        } 
        return; 
    } 
  
    // Return max of elements in range from 
    // index l (query start) to r (query end). 
    static int getMax(int[] st, int n, int l, int r) 
    { 
  
        // Check for erroneous input values 
        if (l < 0 || r > n - 1 || l > r)  
        { 
            System.out.printf("Invalid Input\n"); 
            return -1; 
        } 
  
        return MaxUtil(st, 0, n - 1, l, r, 0); 
    } 
  
    // A recursive function that constructs Segment 
    // Tree for array[ss..se]. si is index of 
    // current node in segment tree st 
    static int constructSTUtil(int arr[], int ss, 
                        int se, int[] st, int si)  
    { 
          
        // If there is one element in array, store 
        // it in current node of segment tree and return 
        if (ss == se)  
        { 
            st[si] = arr[ss]; 
            return arr[ss]; 
        } 
  
        // If there are more than one elements, then 
        // recur for left and right subtrees and 
        // store the max of values in this node 
        int mid = getMid(ss, se); 
  
        st[si] = Math.max(constructSTUtil(arr, ss, mid, st, si * 2 + 1), 
                constructSTUtil(arr, mid + 1, se, st, si * 2 + 2)); 
  
        return st[si]; 
    } 
  
    /* 
    * Function to construct segment tree from 
    given array. This function allocates 
    * memory for segment tree. 
    */
    static int[] constructST(int arr[], int n) 
    { 
  
        // Height of segment tree 
        int x = (int) Math.ceil(Math.log(n) / Math.log(2)); 
  
        // Maximum size of segment tree 
        int max_size = 2 * (int) Math.pow(2, x) - 1; 
  
        // Allocate memory 
        int[] st = new int[max_size]; 
  
        // Fill the allocated memory st 
        constructSTUtil(arr, 0, n - 1, st, 0); 
  
        // Return the constructed segment tree 
        return st; 
    } 
    public static void updateBIT(int n, int index,  
                                        int val , int BITree[] ) 
    { 
        // index in BITree[] is 1 more than  
        // the index in arr[] 
        index++;
        // Traverse all ancestors and add 'val' 
        while(index <= n) 
        { 
        // Add 'val' to current node of BIT Tree 
        BITree[index] += val; 
      
        // Update index to that of parent  
        // in update View 
        index += index & (-index); 
        } 
    } 
    static long mod = 1000000007;
   static long pow(long a , long b , long c)
   {
	   
	   if(b==0)
		   return 1;
	   
	   long ans = pow(a,b/2,c);
	   if(b%2 == 0)
		   return ans*ans%c;
	   
	   return ans*ans%c*a%c;
   }
   
   static long modInverse(long a , long b)
   {
	   return pow(a,b-2,mod);
   }
   
   
   static double d(int x1 , int y1 , int x2 , int y2)
   {
	   double d1 = x1-x2;
	   double d2 = y1-y2;
	   
	   return Math.sqrt(d1*d1-d2*d2);
   }
  

static int low[];
static int p[];
static int parent(int x , int k , int dp[][])
{
while(k > 0)
{
	if(x == -1)
		break;
	
	int up = low[k];
	k -= p[up];
	x = dp[x][up];
}
return x;
}

static void dfs(int n , LinkedList<Integer> arr[] , boolean visited[] , int dp[] , int a[])
{
	visited[n] = true;
	dp[n] = Integer.MIN_VALUE;
	for(Integer i : arr[n])
	{
		if(!visited[i])
		{
			dfs(i,arr,visited,dp,a);
			dp[n] = Math.max(dp[n], Math.max(dp[i],a[i]));
		}
	}
}

static void dfs2(int n , LinkedList<Integer> arr[] , boolean visited[] , int dp[] , int a[] , int prev , int prevmax , int p)
{
	visited[n] = true;
	int temp = Integer.MIN_VALUE;
	
	
	temp = Math.max(prev+1,prevmax+2);
	
	temp = Math.max(temp,a[n]);
	
	if(arr[n].size() == 1 && visited[arr[n].get(0)])
	{
		ans = Math.min(ans,temp);
		
		return;
	}
	int sz = -1;
	if(n==1)
		sz = arr[n].size();
	
	else
		sz = arr[n].size()-1;
	
	int aa[] = new int[sz];
	int pre[] = new int[sz];
	int post[] = new int[sz];
	
	sz = 0;
	for(Integer i : arr[n])
	{
		if(!visited[i])
		{
			temp = Math.max(temp,a[i]+1);
			temp = Math.max(temp,dp[i]+2);
			aa[sz++] = Math.max(dp[i],a[i]);
		}
	}
	ans = Math.min(ans,temp);
	
	
	
	//System.out.println(ans);
	//System.out.println(sz + " " + n);
	pre[0] = aa[0];
	post[sz-1] = aa[sz-1];
	for(int i = 1 ; i < sz ; i++)
	{
		pre[i] = Math.max(pre[i-1] , aa[i]);
	}
	
	for(int i = sz-2 ; i >= 0 ; i--)
	{
		post[i] = Math.max(post[i+1], aa[i]);
	}
	sz = 0;
	for(Integer i : arr[n])
	{
		if(!visited[i])
		{
			int tt = Integer.MIN_VALUE;
			if(sz-1 >= 0)
				tt = Math.max(tt,pre[sz-1]);
			
			if(sz+1 < post.length)
				tt = Math.max(tt,post[sz+1]);
			
			if(p != -1)
				tt = Math.max(tt,a[p]);
			
			
			tt = Math.max(tt , prevmax);
			dfs2(i,arr,visited,dp,a,a[n],tt,n);
			sz++;
		}
	}
	
}
public static void main(String []args) throws IOException
{
	Reader sc = new Reader();
	int n = sc.nextInt();
	LinkedList<Integer> arr[] = new LinkedList[n+1];
	for(int i = 1 ; i <= n ; i++)
	{
		arr[i] = new LinkedList<Integer>();
		
	}
	int a[] = new int[n+1];
	for(int i = 1 ; i <= n ; i++)
	{
		a[i] = sc.nextInt();
	}
	
	for(int i = 1 ; i <= n-1 ; i++)
	{
		int x = sc.nextInt();
		int y = sc.nextInt();
		arr[x].add(y);
		arr[y].add(x);
	}
	
	if(n==1)
		System.out.println(a[1]);
	
	else
	{
	boolean visited[] = new boolean[n+1];
	int dp[] = new int[n+1];
	dfs(1,arr,visited,dp,a);
	
	ans = Integer.MAX_VALUE;
	
	for(int i = 1 ; i <= n ; i++)
	{
		visited[i] = false;
	}
	dfs2(1,arr,visited,dp,a,Integer.MIN_VALUE,Integer.MIN_VALUE,-1);
	System.out.println(ans);
	}
}

}


