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.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Calendar;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.SortedSet;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

/**
 * #
 * 
 * @author pttrung
 */
public class C_Round_408_Div2 {

	public static long MOD = 1000000007;

	public static void main(String[] args) throws FileNotFoundException {
		// PrintWriter out = new PrintWriter(new FileOutputStream(new File(
		// "output.txt")));
		PrintWriter out = new PrintWriter(System.out);
		Scanner in = new Scanner();
		int n = in.nextInt();
		int[] data = new int[n];
		ArrayList<Integer>[] map = new ArrayList[n];
		for (int i = 0; i < n; i++) {
			data[i] = in.nextInt();

			map[i] = new ArrayList();
		}
		for (int i = 0; i < n - 1; i++) {
			int u = in.nextInt() - 1;
			int v = in.nextInt() - 1;
			map[u].add(v);
			map[v].add(u);
		}
//		boolean[] visit = new boolean[n];
//		int com = 0;
//		for (int i = 0; i < n; i++) {
//			if (!visit[i]) {
//				com++;
//				LinkedList<Integer> q = new LinkedList();
//				q.add(i);
//				visit[i] = true;
//				while (!q.isEmpty()) {
//					int node = q.poll();
//					for (int j : map[node]) {
//						if (!visit[j]) {
//							q.add(j);
//							visit[j] = true;
//						}
//					}
//				}
//			}
//		}
//		if (com > 1) {
//			System.out.println("VCL");
//		}

		TreeMap<Integer, Integer> set = new TreeMap();
		for (int i = 0; i < n; i++) {

			set.put(data[i] + 2, set.getOrDefault(data[i] + 2, 0) + 1);
		}
		int result = set.lastKey();
		for (int i = 0; i < n; i++) {
			HashMap<Integer, Integer> cur = new HashMap();
			cur.put(data[i] + 2, 1);
			int tmp = data[i];
			for (int j : map[i]) {
				cur.put(data[j] + 2, cur.getOrDefault(data[j] + 2, 0) + 1);
				tmp = Integer.max(tmp, data[j] + 1);
			}
			Integer v = set.lastKey();
			while (v != null) {
				
				if (!cur.containsKey(v) || set.get(v).compareTo(cur.get(v)) != 0) {
					tmp = Integer.max(tmp, v);
					break;
				} else {
					v = set.lowerKey(v);
				}
			}
			result = Integer.min(result, tmp);

		}
		out.println(result);
		out.close();
	}

	static class Node implements Comparable<Node> {
		int index;
		int val;

		public Node(int index, int val) {
			super();
			this.index = index;
			this.val = val;
		}

		@Override
		public int compareTo(Node o) {
			if (val != o.val) {
				return Integer.compare(val, o.val);
			}
			return Integer.compare(index, o.index);
		}

	}

	public static int[] KMP(String val) {
		int i = 0;
		int j = -1;
		int[] result = new int[val.length() + 1];
		result[0] = -1;
		while (i < val.length()) {
			while (j >= 0 && val.charAt(j) != val.charAt(i)) {
				j = result[j];
			}
			j++;
			i++;
			result[i] = j;
		}
		return result;

	}

	public static boolean nextPer(int[] data) {
		int i = data.length - 1;
		while (i > 0 && data[i] < data[i - 1]) {
			i--;
		}
		if (i == 0) {
			return false;
		}
		int j = data.length - 1;
		while (data[j] < data[i - 1]) {
			j--;
		}
		int temp = data[i - 1];
		data[i - 1] = data[j];
		data[j] = temp;
		Arrays.sort(data, i, data.length);
		return true;
	}

	public static int digit(long n) {
		int result = 0;
		while (n > 0) {
			n /= 10;
			result++;
		}
		return result;
	}

	public static double dist(long a, long b, long x, long y) {
		double val = (b - a) * (b - a) + (x - y) * (x - y);
		val = Math.sqrt(val);
		double other = x * x + a * a;
		other = Math.sqrt(other);
		return val + other;

	}

	public static class Point implements Comparable<Point> {

		int x, y;

		public Point(int start, int end) {
			this.x = start;
			this.y = end;
		}

		@Override
		public int hashCode() {
			int hash = 5;
			hash = 47 * hash + this.x;
			hash = 47 * hash + this.y;
			return hash;
		}

		@Override
		public boolean equals(Object obj) {
			if (obj == null) {
				return false;
			}
			if (getClass() != obj.getClass()) {
				return false;
			}
			final Point other = (Point) obj;
			if (this.x != other.x) {
				return false;
			}
			if (this.y != other.y) {
				return false;
			}
			return true;
		}

		@Override
		public int compareTo(Point o) {
			return Integer.compare(x, o.x);
		}
	}

	public static class FT {

		long[] data;

		FT(int n) {
			data = new long[n];
		}

		public void update(int index, long value) {
			while (index < data.length) {
				data[index] += value;
				index += (index & (-index));
			}
		}

		public long get(int index) {
			long result = 0;
			while (index > 0) {
				result += data[index];
				index -= (index & (-index));
			}
			return result;

		}
	}

	public static long gcd(long a, long b) {
		if (b == 0) {
			return a;
		}
		return gcd(b, a % b);
	}

	public static long pow(long a, long b) {
		if (b == 0) {
			return 1;
		}
		if (b == 1) {
			return a;
		}
		long val = pow(a, b / 2);
		if (b % 2 == 0) {
			return val * val % MOD;
		} else {
			return val * (val * a % MOD) % MOD;

		}
	}

	static class Scanner {

		BufferedReader br;
		StringTokenizer st;

		public Scanner() throws FileNotFoundException {
			// System.setOut(new PrintStream(new
			// BufferedOutputStream(System.out), true));
			br = new BufferedReader(new InputStreamReader(System.in));
			// br = new BufferedReader(new InputStreamReader(new
			// FileInputStream(new File("input.txt"))));
		}

		public String next() {

			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (Exception e) {
					throw new RuntimeException();
				}
			}
			return st.nextToken();
		}

		public long nextLong() {
			return Long.parseLong(next());
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}

		public String nextLine() {
			st = null;
			try {
				return br.readLine();
			} catch (Exception e) {
				throw new RuntimeException();
			}
		}

		public boolean endLine() {
			try {
				String next = br.readLine();
				while (next != null && next.trim().isEmpty()) {
					next = br.readLine();
				}
				if (next == null) {
					return true;
				}
				st = new StringTokenizer(next);
				return st.hasMoreTokens();
			} catch (Exception e) {
				throw new RuntimeException();
			}
		}
	}
}
