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.io.DataInputStream;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

public class main {
	private static InputStream stream;
	private static byte[] buf = new byte[1024];
	private static int curChar;
	private static int numChars;
	private static SpaceCharFilter filter;
	private static PrintWriter pw;
	private static long mod = 1000000000 + 7;
	private static int MAX=1000001;
	private static int block;
	private static void soln(){
		int n=nextInt();
		int max=Integer.MIN_VALUE;
		int cnt=0;
		int ind=-1;
		int cnt1=0;
		int max1=Integer.MIN_VALUE;
		int[] arr=new int[n];
		for(int i=0;i<n;i++){
			int x=nextInt();
			arr[i]=x;
			if(x>max){
				max1=max;
				cnt1=cnt;
				max=x;
				cnt=1;
				ind=i;
			}else if(x==max)
				cnt++;
			else if(x>max1){
				max1=x;
				cnt1=1;
			}else if(x==max1)
				cnt1++;
		}
		int[] cnta=new int[n];
		int[] cntb=new int[n];
		int cnt2=0;
		for(int i=0;i<n-1;i++){
			int x=nextInt()-1;
			int y=nextInt()-1;
			if(cnt!=1 && (arr[x]==max && arr[y]==max)){
				cnta[x]++;
				cnta[y]++;
			}else if(cnt!=1 &&arr[y]==max){
				cntb[x]++;
			}
			else if(cnt!=1 &&arr[x]==max){
				cntb[y]++;
			}
			else if(cnt==1){
				if(x==ind && arr[y]==max1)
					cnt2++;
				else if(y==ind && arr[x]==max1)
					cnt2++;
			}
		}
		if(n==1)
			pw.println(max);
		else if(n==2 && cnt==1)
			pw.println(max);
		else if(n==2 && cnt==2)
			pw.println(max+1);
		else if(cnt==1){
			if(max>=max1+2)
				pw.println(max);
			else{
				if(cnt2==cnt1)
					pw.println(max);
				else
					pw.println(max+1);
			}
		}
		else{
			int i;
			for(i=0;i<n;i++)
				if(cnta[i]==cnt-1 || cntb[i]==cnt){
					//System.out.println(cnt);
					pw.println(max+1);
					break;
				}
			if(i==n)
				pw.println(max+2);
		}
	}
	private static void BFS(LinkedList<Edge>[] l,int n,int[] ps){
		Queue<Integer> q=new LinkedList<>();
		HashSet<Integer> s=new HashSet<>();
		boolean[] v1=new boolean[n];
		int cnt=0;
		for(int i=0;i<ps.length;i++){
			if(!v1[ps[i]-1]){
				q.add(ps[i]-1);
				v1[ps[i]-1]=true;
				cnt++;
			}
		}
		pw.println(cnt-1);
		boolean[] v2=new boolean[n-1];
		while(!q.isEmpty()){
			int x=q.poll();
			//System.out.println(x);
			Iterator<Edge> it=l[x].listIterator();
			while(it.hasNext()){
				Edge e=it.next();
				if(!v2[e.i]){
					v2[e.i]=true;
					if(e.x==x){
						if(v1[e.y])
							s.add(e.i+1);
						else{
							v1[e.y]=true;
							q.add(e.y);
						}
					}else{
						if(v1[e.x])
							s.add(e.i+1);
						else{
							v1[e.x]=true;
							q.add(e.x);
						}
					}
				}
			}
		}
		for(int x:s)
			pw.print(x+" ");
	}
	private static class Treap{
		Node root;
		int[] random;
		int cnt;
		Random rnd=new Random();
		private static class Node{
			int cnt;
			int prio;
			int val;
			int max=Integer.MIN_VALUE;
			Node left;
			Node right;
		}
		private int count(Node p){
			return p==null?0:p.cnt;
		}
		private int max(Node p){
			return p==null?Integer.MIN_VALUE:p.max;
		}
		void update(Node p){
			p.cnt=1+count(p.left)+count(p.right);
			p.max=Math.max(p.val,Math.max(max(p.left),max(p.right)));
		}
		Node merge(Node l,Node r){
			Node tmp;
			if(l==null)
				tmp=r;
			else if(r==null)
				tmp=l;
			else if(l.prio<r.prio){
				l.right=merge(l.right,r);
				tmp=l;
			}else{
				r.left=merge(l,r.left);
				tmp=r;
			}
			update(tmp);
			return tmp;
		}
		Node L,R;
		void split(Node t,int key){
			if(t==null){
				L=R=null;
				return;
			}
			if(key<=count(t.left)){
				split(t.left,key);
				t.left=R;
				R=t;
			}else{
				split(t.right,key-count(t.left)-1);
				t.right=L;
				L=t;
			}
			update(t);
		}
		private Node add(Node t,Node it,int ind){
			if(t==null){
				it.prio=rnd.nextInt();
				return it;
			}
			/*else if(it.prio<t.prio){
				split(t,ind);
				it.left=L;
				it.right=R;
				tmp=it;
			}else{*/
			else if(ind<=count(t.left)){
				t.left=add(t.left,it,ind);
				if(t.left.prio>t.prio)
					t=rotate(t,t.left);
			}
			else{
				t.right=add(t.right,it,ind-count(t.left)-1);
				if(t.right.prio>t.prio)
					t=rotate(t,t.right);
			}
			//System.out.println(t+" "+t.left);
			update(t);
			//System.out.println("s");
			return t;
		}
		public void add(int ind,int val){
			Node it=new Node();
			it.val=val;
			//it.prio=random[cnt++];
			it.cnt=1;
			it.max=val;
			root=add(root,it,ind);
			//System.out.println("s");
		}
		public int max(int a,int b){
			split(root,b);
			Node R1=R;
			split(L,a-1);
			int res=max(R);
			root=merge(merge(L,R),R1);
			return res;
		}
		public int query(Node root,int i,int j,int qi,int qj){
			if(root==null || i>=qj || j<=qi)return Integer.MIN_VALUE;
			if(qi<=i && qj>=j)return root.max;
			int res=Integer.MIN_VALUE;
			res=Math.max(res,query(root.left,i,i+count(root.left),qi,qj));
			res=Math.max(res,query(root.right,i+count(root.left)+1,j,qi,qj));
			if(i+count(root.left)>=qi && i+count(root.left)<qj)
				res=Math.max(res,root.val);
			return res;
		}
		private Node rotate(Node p,Node s){
			if(p.left!=null && p.left.equals(s)){
				p.left=s.right;
				s.right=p;
			}else{
				p.right=s.left;
				s.left=p;
			}
			update(p);
			update(s);
			return s;
		}
		public int[] getRandomPermutation(int n) {
			Random rnd=new Random();
			int[] res = new int[n];
			for (int i = 0; i < n; i++) {
				res[i] = i;
			}
			for (int i = res.length; i > 1; i--) {
				int j = rnd.nextInt(i);
				int t = res[i - 1];
				res[i - 1] = res[j];
				res[j] = t;
			}
			return res;
		}
	}
	private static class DSU{
		int[] parent;
		public DSU(int n){
			parent=new int[n];
			for(int i=0;i<n;i++)
				parent[i]=i;
		}
		int find(int i){
	        while(parent[i] !=i){
	        	parent[i]=parent[parent[i]];
	        	i=parent[i];
	        }
	        return i;
	    }
		void Union(int x, int y){
	        int xset = find(x);
	        int yset = find(y);
	        parent[yset]=yset;
	        parent[xset] = yset;
	    }
	}
	/*private static void dfs(int cur,LinkedList<Edge>[] l,int[] val,int n){
		HashSet<Integer> mst=new HashSet<>();
		int[] par=new int[n];
		PriorityQueue<Pair> key=new PriorityQueue<>();
		key.add(new Pair());
		par[0]=-1;
		for(int count=0;count<n-1;count++){
			
		
	}*/
	private static class Edge{
		int x;
		int y;
		int i;
		public Edge(int a,int b,int c){
			x=a; y=b;i=c;
		}
	}
	private static long pow(long a, long b, long c) {
		if (b == 0)
			return 1;
		long p = pow(a, b / 2, c);
		p = (p * p) % c;
		return (b % 2 == 0) ? p : (a * p) % c;
	}
	
	private static class Mo implements Comparable<Mo>{
		int l;
		int r;
		int i;
		public Mo(int a,int b,int ind) {
			l=a;r=b;i=ind;
		}
		@Override
		public int compareTo(Mo arg0) {
			int b1=this.l/block;
			int b2=arg0.l/block;
			return (b1!=b2)?(b1-b2):(this.r-arg0.r);
		}
	}

	private static long gcd(long n, long l) {
		if (l == 0)
			return n;
		return gcd(l, n % l);
	}

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

	private static long min(long a, long b) {
		if (a < b)
			return a;
		return b;
	}

	public static void main(String[] args) throws Exception {
		new Thread(null,new Runnable(){
			@Override
			public void run() {
				/*try {
					InputReader(new FileInputStream("C:\\Users\\hardik\\Desktop\\C-small-1-attempt1.in"));
				} catch (FileNotFoundException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}*/
				InputReader(System.in);
				pw = new PrintWriter(System.out);
				/*try {
					pw=new PrintWriter(new FileOutputStream("C:\\Users\\hardik\\Desktop\\out.txt"));
				} catch (FileNotFoundException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}*/
				soln();
				pw.close();
			}
		},"1",1<<26).start();
	}

	public static void InputReader(InputStream stream1) {
		stream = stream1;
	}

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

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

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

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

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

	private static String nextToken() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isSpaceChar(c));
		return res.toString();
	}

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

	private static int[] nextIntArray(int n) {
		int[] arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = nextInt();
		}
		return arr;
	}

	private static long[] nextLongArray(int n) {
		long[] arr = new long[n];
		for (int i = 0; i < n; i++) {
			arr[i] = nextLong();
		}
		return arr;
	}

	private static void pArray(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
		return;
	}

	private static void pArray(long[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
		return;
	}

	private static boolean isSpaceChar(int c) {
		if (filter != null)
			return filter.isSpaceChar(c);
		return isWhitespace(c);
	}
	private static char nextChar() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		char c1=(char)c;
		while(!isSpaceChar(c))
			c=read();
		return c1;
}
	private interface SpaceCharFilter {
		public boolean isSpaceChar(int ch);
	}
}