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.*;
import java.lang.Math.*;

public class MainA
{

	public static int mod = 20000;
	public static long[] val;
	public static long[] arr;
	static int max = (int) 1e9 + 7;

	public static void main(String[] args) throws java.lang.Exception
	{
		InputReader in = new InputReader(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int n=in.nextInt();
		int a[]=new int[n];
		int ma[]=new int[2];
		int max=Integer.MIN_VALUE;
		for(int i=0;i<n;i++)
		{
			a[i]=in.nextInt();
			max=Math.max(max,a[i]);
			
		}
		for(int i=0;i<n;i++)
		{
			if(a[i]+2>max)
			{
				ma[a[i]+2-max-1]++;
			}
		}
		
		
		LinkedList<Integer> adj[]=new LinkedList[n];
		for(int i=0;i<n;i++)adj[i]=new LinkedList();
		for(int i=0;i<n-1;i++)
		{
			int x=in.nextInt()-1;
			int y=in.nextInt()-1;
			adj[x].add(y);
			adj[y].add(x);
		}
		
		long ans[]=new long[n];
		Arrays.fill(ans,max);
		for(int i=0;i<n;i++)
		{
			int key=i;
			if(a[key]+2>max)
			{
				ma[a[key]+2-max-1]--;
			}
			
			Iterator<Integer> it=adj[i].listIterator();
			while(it.hasNext())
			{
				int s=(int)it.next();
				if(a[s]+2>max)
				{
					ma[a[s]+2-max-1]--;
					if(a[s]==max)
					ans[i]=max+1;	
				}
				
			}
			if(ma[1]!=0)
			{
				ans[i]=max+2;
			}
			else if(ma[0]!=0)
			{
				ans[i]=max+1;
			}
			if(a[key]+2>max)
			ma[a[key]+2-max-1]++;
			
			it=adj[i].listIterator();
			while(it.hasNext())
			{
				int s=it.next();
				if(a[s]+2>max)
				{
					ma[a[s]+2-max-1]++;
				}
			}
		//	out.println(ans[i]);
			
		}
		long min=ans[0];
		for(int i=1;i<n;i++)
		{
			min=Math.min(min,ans[i]);
		}
		out.println(min);
		out.close();
	}

	class CycleUnd
	{
	    int V, E;    // V-> no. of vertices & E->no.of edges
	    Edge edge[]; // /collection of all edges
	 
	    class Edge
	    {
	        int src, dest;
	    };
	 
	    // Creates a graph with V vertices and E edges
	    CycleUnd(int v,int e)
	    {
	        V = v;
	        E = e;
	        edge = new Edge[E];
	        for (int i=0; i<e; ++i)
	            edge[i] = new Edge();
	    }
	 
	    // A utility function to find the subset of an element i
	    int find(Pairs parent[], int i)
	    {
	        if (parent[i].x != i)
	            parent[i].x=find(parent,parent[i].x);
	        return parent[i].x;
	    }
	 
	    // A utility function to do union of two parent
	    void Union(Pairs parent[], int x, int y)
	    {
	        int xroot = find(parent, x);
	        int yroot = find(parent, y);
	        if (parent[xroot].y < parent[yroot].y)
	            parent[xroot].x = yroot;
	        else if (parent[xroot].y > parent[yroot].y)
	            parent[yroot].x = xroot;
	     
	        // If ranks are same, then make one as root and increment
	        // its rank by one
	        else
	        {
	            parent[yroot].x = xroot;
	            parent[xroot].y++;
	        }
	    }
	 
	 
	    // The main function to check whether a given graph
	    // contains cycle or not
	    int isCycle(CycleUnd graph)
	    {
	        
	        Pairs parent[] = new Pairs[graph.V];
	 
	       
	        for (int i=0; i<graph.V; ++i)
	        {
	        	parent[i]=new Pairs(i,0);
	        }
	 
	       
	        for (int i = 0; i < graph.E; ++i)
	        {
	            int x = graph.find(parent, graph.edge[i].src);
	            int y = graph.find(parent, graph.edge[i].dest);
	 
	            if (x == y)
	                return 1;
	 
	            graph.Union(parent, x, y);
	        }
	        return 0;
	    }
	}
	
	static void spiralPrint(int m, int n, int a[][])
    {
        int i, k = 0, l = 0;
        /*  k - starting row index
        m - ending row index
        l - starting column index
        n - ending column index
        i - iterator
        */
          
        while (k < m && l < n)
        {
            // Print the first row from the remaining rows
            for (i = l; i < n; ++i)
            {
                System.out.print(a[k][i]+" ");
            }
            k++;
  
            // Print the last column from the remaining columns 
            for (i = k; i < m; ++i)
            {
                System.out.print(a[i][n-1]+" ");
            }
            n--;
  
            // Print the last row from the remaining rows */
            if ( k < m)
            {
                for (i = n-1; i >= l; --i)
                {
                    System.out.print(a[m-1][i]+" ");
                }
                m--;
            }
  
            // Print the first column from the remaining columns */
            if (l < n)
            {
                for (i = m-1; i >= k; --i)
                {
                    System.out.print(a[i][l]+" ");
                }
                l++;    
            }        
        }
    }
	
	
	public static int binarySearch(int n,int a[],int x)
	{
		int l=0;int r=n-1;
		while(l<=r)
		{
			int mid=(l+r)/2;
			if(a[mid]==x)
			{
				return mid;
			}
			else if(a[mid]<x)
			{
				l=mid+1;
			}
			else 
				r=mid-1;
		}
		return -1;
	}
	public static void sieve()
	{
		int n=(int)1e7;
		int prime[]=new int[n+1];
		for(int i=2;i<=n;i++)
		{
			prime[i]=i;
		}
		
		for(int i=2;i*i<=n;i++)
		{
			if(prime[i]==i)
			{
				for(int j=2*i;j<=n;j+=i)
				{
					if(prime[j]==j)
					{
						prime[j]=i;
					}
				}
			}
		}
	}
	static class Pairs implements Comparable<Pairs>
	{
		int x;
		int y;

		Pairs(int a, int b)
		{
			x = a;
			y = b;
		}

		@Override
		public int compareTo(Pairs o)
		{
			// TODO Auto-generated method stub
			if (x == o.x)
				return Integer.compare(y, o.y);
			else
				return Long.compare(-x, -o.x);
		}

	}

	public static void debug(Object... o) 
	{
		System.out.println(Arrays.deepToString(o));
	}

	public static boolean isPal(String s) 
	{
		for (int i = 0, j = s.length() - 1; i <= j; i++, j--)
		{
			if (s.charAt(i) != s.charAt(j))
				return false;
		}
		return true;
	}

	public static String rev(String s)
	{
		StringBuilder sb = new StringBuilder(s);
		sb.reverse();
		return sb.toString();
	}

	public static long gcd(long x, long y)
	{
		if (y == 0)
			return x;
		if (x % y == 0)
			return y;
		else
			return gcd(y, x % y);
	}

	public static int gcd(int x, int y)
	{
		if(y==0)
			return x;
		if (x % y == 0)
			return y;
		else
			return gcd(y, x % y);
	}

	public static long gcdExtended(long a, long b, long[] x) 
	{

		if (a == 0) 
		{
			x[0] = 0;
			x[1] = 1;
			return b;
		}
		long[] y = new long[2];
		long gcd = gcdExtended(b % a, a, y);

		x[0] = y[1] - (b / a) * y[0];
		x[1] = y[0];

		return gcd;
	}

	
	

	public static long max(long a, long b) 
	{
		if (a > b)
			return a;
		else
			return b;
	}

	public static long min(long a, long b)
	{
		if (a > b)
			return b;
		else
			return a;
	}

	public static long[][] mul(long a[][], long b[][])
	{
		long c[][] = new long[2][2];
		c[0][0] = a[0][0] * b[0][0] + a[0][1] * b[1][0];
		c[0][1] = a[0][0] * b[0][1] + a[0][1] * b[1][1];
		c[1][0] = a[1][0] * b[0][0] + a[1][1] * b[1][0];
		c[1][1] = a[1][0] * b[0][1] + a[1][1] * b[1][1];

		return c;
	}

	public static long[][] pow(long n[][], long p, long m)
	{
		long result[][] = new long[2][2];
		result[0][0] = 1;
		result[0][1] = 0;
		result[1][0] = 0;
		result[1][1] = 1;

		if (p == 0)
			return result;
		if (p == 1)
			return n;
		while (p != 0)
		{
			if (p % 2 == 1)
				result = mul(result, n);
			//System.out.println(result[0][0]);
			for (int i = 0; i < 2; i++)
			{
				for (int j = 0; j < 2; j++)
				{
					if (result[i][j] >= m)
						result[i][j] %= m;
				}
			}

			p >>= 1;
			n = mul(n, n);
			// System.out.println(1+" "+n[0][0]+" "+n[0][1]+" "+n[1][0]+" "+n[1][1]);
			for (int i = 0; i < 2; i++) 
			{
				for (int j = 0; j < 2; j++)
				{
					if (n[i][j] >= m)
						n[i][j] %= m;
				}
			}
		}
		return result;
	}
	public static long pow(long n,long p, long m)
	{
		long result=1;
		if(p==0)return 1;
		if(p==1)return n%m;
		while(p!=0)
		{
			if(p%2==1)result=(result*n)%m;
			p >>=1;
			n=(n*n)%m;
		}
		return result;
	}
	public static long pow(long n, long p) 
	{
		long result = 1;
		if (p == 0)
			return 1;
		if (p == 1)
			return n;
		while (p != 0)
		{
			if (p % 2 == 1)
				result *= n;
			p >>= 1;
			n *= n;
		}
		return result;
	}

	static class InputReader {

		private final InputStream stream;
		private final byte[] buf = new byte[8192];
		private int curChar, snumChars;
		private SpaceCharFilter filter;

		public InputReader(InputStream stream)
		{
			this.stream = stream;
		}

		public int snext()
		{
			if (snumChars == -1)
				throw new InputMismatchException();
			if (curChar >= snumChars)
			{
				curChar = 0;
				try 
				{
					snumChars = stream.read(buf);
				}
				catch (IOException e)
				{
					throw new InputMismatchException();
				}
				if (snumChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public int nextInt()
		{
			int c = snext();
			while (isSpaceChar(c))
			{
				c = snext();
			}
			int sgn = 1;
			if (c == '-')
			{
				sgn = -1;
				c = snext();
			}
			int res = 0;
			do
			{
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = snext();
			}
			while (!isSpaceChar(c));
			return res * sgn;
		}

		public long nextLong()
		{
			int c = snext();
			while (isSpaceChar(c))
			{
				c = snext();
			}
			int sgn = 1;
			if (c == '-') 
			{
				sgn = -1;
				c = snext();
			}
			long res = 0;
			do 
			{
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = snext();
			}
			while (!isSpaceChar(c));
			return res * sgn;
		}

		public int[] nextIntArray(int n)
		{
			int a[] = new int[n];
			for (int i = 0; i < n; i++)
			{
				a[i] = nextInt();
			}
			return a;
		}

		public long[] nextLongArray(int n)
		{
			long a[] = new long[n];
			for (int i = 0; i < n; i++) 
			{
				a[i] = nextInt();
			}
			return a;
		}

		public String readString()
		{
			int c = snext();
			while (isSpaceChar(c))
			{
				c = snext();
			}
			StringBuilder res = new StringBuilder();
			do 
			{
				res.appendCodePoint(c);
				c = snext();
			} 
			while (!isSpaceChar(c));
			return res.toString();
		}

		public String nextLine()
		{
			int c = snext();
			while (isSpaceChar(c))
				c = snext();
			StringBuilder res = new StringBuilder();
			do
			{
				res.appendCodePoint(c);
				c = snext();
			}
			while (!isEndOfLine(c));
			return res.toString();
		}

		public boolean isSpaceChar(int c) 
		{
			if (filter != null)
				return filter.isSpaceChar(c);
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		private boolean isEndOfLine(int c)
		{
			return c == '\n' || c == '\r' || c == -1;
		}

		public interface SpaceCharFilter 
		{
			public boolean isSpaceChar(int ch);
		}
	}
}