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 a_{i}.

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:  Bank x is online. That is, bank x is not hacked yet.  Bank x is neighboring to some offline bank.  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·10^5) — the total number of banks.

The second line contains n integers a_1, a_2, ..., a_{n} ( - 10^9 ≤ a_{i} ≤ 10^9) — the strengths of the banks.

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

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.

Difficulty: interview

Starter code:

Solutions:
def sol():

    n = int(input())
    st = list(map(int, input().split(' ')))
    d = {}
    for x in range(n):
        d[x] = []

    st = [(st[i], i) for i in range(len(st))]
    st = sorted(st)

    for a0 in range(n - 1):
        u, v = map(int, input().split(' '))
        u, v = u - 1, v - 1
        d[u].append(v)
        d[v].append(u)

    hardest = []
    almost = []

    single_hardest = st[-1][0]

    for x in st[::-1]:
        if x[0] == single_hardest:
            hardest.append(x[1])
        elif x[0] == single_hardest-1:
            almost.append(x[1])
        else:
            break

    def inter(a, b):
        c = []
        for x in a:
            if x in b:
                c.append(x)
        return c

    lower_bound = single_hardest

    inte = d[hardest[0]]+[hardest[0]]
    for h in hardest[1:]:
        inte = inter(inte, d[h]+[h])

    if not inte:
        return (single_hardest+2)

    if len(hardest) > 1:
        return single_hardest+1

    # hardest is len 1
    if not almost:
        return single_hardest

    cand = st[-1][1]

    for h in almost:
        if h not in d[cand]:
            return single_hardest+1
    return single_hardest

print(sol())

n = int(input())

strengths = list(map(int, input().split()))
max_strength = max(strengths)

count_max = strengths.count(max_strength)
count_second_place = strengths.count(max_strength - 1)

maxes = [0 for i in range(n)]
second_places = [0 for i in range(n)]

for i in range(n - 1):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    if strengths[a] == max_strength:
        maxes[b] += 1
    elif strengths[a] == max_strength - 1:
        second_places[b] += 1

    if strengths[b] == max_strength:
        maxes[a] += 1
    elif strengths[b] == max_strength - 1:
        second_places[a] += 1

total_max = 1000000009
for i in range(n):
    here = 0
    if strengths[i] < max_strength:
        if maxes[i] == count_max:
            here = max_strength + 1
        else:
            here = max_strength + 2
    else:
        if count_max == 1:
            if second_places[i] == count_second_place:
                here = max_strength
            else:
                here = max_strength + 1
        else:
            if maxes[i] == count_max - 1:
                here = max_strength + 1
            else:
                here = max_strength + 2
    total_max = min(total_max, here)

print(total_max)


import sys

def solve():
    n = int(sys.stdin.readline().rstrip())
    a = [int(i) for i in sys.stdin.readline().split()]
    Adj = [[] for i in range(n)]

    for i in range(n - 1):
        u, v = map(int, sys.stdin.readline().split())
        u, v = u-1, v-1
        Adj[u].append(v)
        Adj[v].append(u)

    max_v = max(a)
    max_n = a.index(max_v)
    num_m = sum(ai == max_v for ai in a)

    if num_m == 1:
        ans = max_v

        rinsetu = [False] * n

        for u in Adj[max_n]:
            rinsetu[u] = True

        rinsetu[max_n] = True

        for u in range(n):
            if rinsetu[u]:
                continue
            if a[u] == max_v - 1:
                ans = max_v + 1
                break
    else:
        for u in range(n):
            cnt = 0

            if a[u] == max_v:
                cnt += 1

            for v in Adj[u]:
                if a[v] == max_v:
                    cnt += 1

            if cnt == num_m:
                ans = max_v + 1
                break
        else:
            ans = max_v + 2

    print(ans)


def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def __starting_point():
    solve()
__starting_point()

import sys

def solve():
    n = int(sys.stdin.readline().rstrip())
    a = [int(i) for i in sys.stdin.readline().split()]
    Adj = [[] for i in range(n)]

    for i in range(n - 1):
        u, v = map(int, sys.stdin.readline().split())
        u, v = u-1, v-1
        Adj[u].append(v)
        Adj[v].append(u)

    max_v = max(a)
    max_n = a.index(max_v)
    num_m = sum(ai == max_v for ai in a)

    if num_m == 1:
        ans = max_v

        rinsetu = [False] * n

        for u in Adj[max_n]:
            rinsetu[u] = True

        rinsetu[max_n] = True

        for u in range(n):
            if rinsetu[u]:
                continue
            if a[u] == max_v - 1:
                ans = max_v + 1
                break
    else:
        for u in range(n):
            cnt = 0

            if a[u] == max_v:
                cnt += 1

            for v in Adj[u]:
                if a[v] == max_v:
                    cnt += 1

            if cnt == num_m:
                ans = max_v + 1
                break
        else:
            ans = max_v + 2

    print(ans)


def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def __starting_point():
    solve()
__starting_point()

import sys

def solve():
    n = int(sys.stdin.readline().rstrip())
    a = [int(i) for i in sys.stdin.readline().split()]
    Adj = [[] for i in range(n)]

    for i in range(n - 1):
        u, v = map(int, sys.stdin.readline().split())
        u, v = u-1, v-1
        Adj[u].append(v)
        Adj[v].append(u)

    max_v = max(a)
    num_m = sum(ai == max_v for ai in a)

    if num_m == 1:
        ans = max_v
        max_n = a.index(max_v)

        rinsetu = set(Adj[max_n])
        rinsetu.add(max_n)

        for u in range(n):
            if u in rinsetu:
                continue
            if a[u] == max_v - 1:
                ans = max_v + 1
                break
    else:
        for u in range(n):
            cnt = 0

            if a[u] == max_v:
                cnt += 1

            for v in Adj[u]:
                if a[v] == max_v:
                    cnt += 1

            if cnt == num_m:
                ans = max_v + 1
                break
        else:
            ans = max_v + 2

    print(ans)


def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def __starting_point():
    solve()
__starting_point()

import sys
n=int(sys.stdin.readline())
d=list(map(int,sys.stdin.readline().split()))
s=[[] for g in d]
mxpt=[-2e9,-2e9]
mxcnt=[0,0]
for i in d:
	if i>mxpt[0]:
		mxpt[1]=mxpt[0]
		mxcnt[1]=mxcnt[0]
		mxpt[0]=i
		mxcnt[0]=1
	elif i==mxpt[0]:
		mxcnt[0]+=1
	elif i>mxpt[1]:
		mxpt[1]=i
		mxcnt[1]=1
	else: mxcnt[1]+=(i==mxpt[1])
for i in range(1,n):
	a,b=map(int,sys.stdin.readline().split())
	a-=1;
	b-=1;
	s[a]+=[b]
	s[b]+=[a]

mx=int(2e9)
for i in range(n):
	nmx=[]+mxcnt
	tmpmax=d[i]
	for k in s[i]:
		if d[k]==mxpt[0]:			
			nmx[0]-=1
		elif d[k]==mxpt[1]:			
			nmx[1]-=1

	if nmx[0]!=mxcnt[0]:
		tmpmax=mxpt[0]+1
	elif nmx[1]!=mxcnt[1]:
		tmpmax=max(tmpmax,mxpt[1]+1)

	if d[i]==mxpt[0]:
		nmx[0]-=1
	elif d[i]==mxpt[1]:
		nmx[1]-=1

	if nmx[0]:
		tmpmax=mxpt[0]+2
	elif nmx[1]:
		tmpmax=max(mxpt[1]+2,tmpmax)
	mx=min(mx,tmpmax)
print(mx)

import sys
n=int(sys.stdin.readline())
d=list(map(int,sys.stdin.readline().split()))
s=[[] for g in d]
mx_tmp=max(d)
mx_tmp2=max(g for g in d+[-2e9] if g<mx_tmp)
mxpt=[mx_tmp,mx_tmp2]
mxcnt=[d.count(mx_tmp),d.count(mx_tmp2)]
for i in range(1,n):
	a,b=map(int,sys.stdin.readline().split())
	a-=1;
	b-=1;
	s[a]+=[b]
	s[b]+=[a]

mx=int(2e9)
for i in range(n):
	nmx=[]+mxcnt
	tmpmax=d[i]
	for k in s[i]:
		if d[k]==mxpt[0]:			
			nmx[0]-=1
		elif d[k]==mxpt[1]:			
			nmx[1]-=1

	if nmx[0]!=mxcnt[0]:
		tmpmax=mxpt[0]+1
	elif nmx[1]!=mxcnt[1]:
		tmpmax=max(tmpmax,mxpt[1]+1)

	if d[i]==mxpt[0]:
		nmx[0]-=1
	elif d[i]==mxpt[1]:
		nmx[1]-=1

	if nmx[0]:
		tmpmax=mxpt[0]+2
	elif nmx[1]:
		tmpmax=max(mxpt[1]+2,tmpmax)
	mx=min(mx,tmpmax)
print(mx)

import sys
def solve():
	n=int(sys.stdin.readline())
	d=list(map(int,sys.stdin.readline().split()))
	s=[[] for g in d]
	mx_tmp=max(d)
	mx_tmp2=max(g for g in d+[-2e9] if g<mx_tmp)
	mxpt=[mx_tmp,mx_tmp2]
	mxcnt=[d.count(mx_tmp),d.count(mx_tmp2)]
	for i in range(1,n):
		a,b=map(int,sys.stdin.readline().split())
		a-=1;
		b-=1;
		s[a]+=[b]
		s[b]+=[a]

	mx=int(2e9)
	for i in range(n):
		nmx=[]+mxcnt
		tmpmax=d[i]
		for k in s[i]:
			if d[k]==mxpt[0]:			
				nmx[0]-=1
			elif d[k]==mxpt[1]:			
				nmx[1]-=1

		if nmx[0]!=mxcnt[0]:
			tmpmax=mxpt[0]+1
		elif nmx[1]!=mxcnt[1]:
			tmpmax=max(tmpmax,mxpt[1]+1)

		if d[i]==mxpt[0]:
			nmx[0]-=1
		elif d[i]==mxpt[1]:
			nmx[1]-=1

		if nmx[0]:
			tmpmax=mxpt[0]+2
		elif nmx[1]:
			tmpmax=max(mxpt[1]+2,tmpmax)
		mx=min(mx,tmpmax)
	print(mx)

def __starting_point():
    solve()
__starting_point()

import sys
def solve():
	n=int(sys.stdin.readline())
	d=list(map(int,sys.stdin.readline().split()))
	s=[[] for g in d]
	mx_tmp=max(d)
	mx_tmp2=max(g for g in d+[-2e9] if g<mx_tmp)
	mxpt=[mx_tmp,mx_tmp2]
	mxcnt=[d.count(mx_tmp),d.count(mx_tmp2)]
	for i in range(1,n):
		a,b=map(int,sys.stdin.readline().split())
		a-=1;
		b-=1;
		s[a]+=[b]
		s[b]+=[a]

	mx=int(2e9)
	for i in range(n):
		nmx=[]+mxcnt
		tmpmax=d[i]
		for k in s[i]:
			if d[k]==mxpt[0]:			
				nmx[0]-=1
			elif d[k]==mxpt[1]:			
				nmx[1]-=1

		if nmx[0]!=mxcnt[0]:
			tmpmax=mxpt[0]+1
		elif nmx[1]!=mxcnt[1]:
			tmpmax=max(tmpmax,mxpt[1]+1)

		if d[i]==mxpt[0]:
			nmx[0]-=1
		elif d[i]==mxpt[1]:
			nmx[1]-=1

		if nmx[0]:
			tmpmax=mxpt[0]+2
		elif nmx[1]:
			tmpmax=max(mxpt[1]+2,tmpmax)
		mx=min(mx,tmpmax)
	print(mx)

def __starting_point():
    solve()
__starting_point()

import sys
def solve():
	n=int(sys.stdin.readline())
	d=list(map(int,sys.stdin.readline().split()))
	s=[[] for g in d]
	mx_tmp=max(d)
	mx_tmp2=max(g for g in d+[-2e9] if g<mx_tmp)
	mxpt=[mx_tmp,mx_tmp2]
	mxcnt=[d.count(mx_tmp),d.count(mx_tmp2)]
	for i in range(1,n):
		a,b=map(int,sys.stdin.readline().split())
		
		a-=1;
		b-=1;
		s[a]+=[b]
		s[b]+=[a]

	mx=int(2e9)
	for i in range(n):
		nmx=[]+mxcnt
		tmpmax=d[i]
		for k in s[i]:
			if d[k]==mxpt[0]:			
				nmx[0]-=1
			elif d[k]==mxpt[1]:			
				nmx[1]-=1

		if nmx[0]!=mxcnt[0]:
			tmpmax=mxpt[0]+1
		elif nmx[1]!=mxcnt[1]:
			tmpmax=max(tmpmax,mxpt[1]+1)

		if d[i]==mxpt[0]:
			nmx[0]-=1
		elif d[i]==mxpt[1]:
			nmx[1]-=1

		if nmx[0]:
			tmpmax=mxpt[0]+2
		elif nmx[1]:
			tmpmax=max(mxpt[1]+2,tmpmax)
		mx=min(mx,tmpmax)
	print(mx)

def __starting_point():
    solve()
__starting_point()

import sys
n=int(sys.stdin.readline())
d=list(map(int,sys.stdin.readline().split()))
s=[[] for g in d]
mx_tmp=max(d)
mx_tmp2=max(g for g in d+[-2e9] if g<mx_tmp)
mxpt=[mx_tmp,mx_tmp2]
mxcnt=[d.count(mx_tmp),d.count(mx_tmp2)]
for i in range(1,n):
	a,b=list(map(int,sys.stdin.readline().split()))

	a-=1;
	b-=1;
	s[a]+=[b]
	s[b]+=[a]

mx=int(2e9)
for i in range(n):
	nmx=[]+mxcnt
	tmpmax=d[i]
	for k in s[i]:
		if d[k]==mxpt[0]:			
			nmx[0]-=1
		elif d[k]==mxpt[1]:			
			nmx[1]-=1

	if nmx[0]!=mxcnt[0]:
		tmpmax=mxpt[0]+1
	elif nmx[1]!=mxcnt[1]:
		tmpmax=max(tmpmax,mxpt[1]+1)

	if d[i]==mxpt[0]:
		nmx[0]-=1
	elif d[i]==mxpt[1]:
		nmx[1]-=1

	if nmx[0]:
		tmpmax=mxpt[0]+2
	elif nmx[1]:
		tmpmax=max(mxpt[1]+2,tmpmax)
	mx=min(mx,tmpmax)
print(mx)



import sys
def solve():
	n=int(sys.stdin.readline())
	d=list(map(int,sys.stdin.readline().split()))
	s=[[] for g in d]
	mx_tmp=max(d)
	mx_tmp2=max(g for g in d+[-2e9] if g<mx_tmp)
	mxpt=[mx_tmp,mx_tmp2]
	mxcnt=[d.count(mx_tmp),d.count(mx_tmp2)]
	for i in range(1,n):
		a,b=map(int,sys.stdin.readline().split())
		
		a-=1;
		b-=1;
		s[a]+=[b]
		s[b]+=[a]

	mx=int(2e9)
	for i in range(n):
		nmx=[]+mxcnt
		tmpmax=d[i]
		for k in s[i]:
			if d[k]==mxpt[0]:			
				nmx[0]-=1
			elif d[k]==mxpt[1]:			
				nmx[1]-=1

		if nmx[0]!=mxcnt[0]:
			tmpmax=mxpt[0]+1
		elif nmx[1]!=mxcnt[1]:
			tmpmax=max(tmpmax,mxpt[1]+1)

		if d[i]==mxpt[0]:
			nmx[0]-=1
		elif d[i]==mxpt[1]:
			nmx[1]-=1

		if nmx[0]:
			tmpmax=mxpt[0]+2
		elif nmx[1]:
			tmpmax=max(mxpt[1]+2,tmpmax)
		mx=min(mx,tmpmax)
	print(mx)

def __starting_point():
    solve()
__starting_point()

import sys

def solve():
    n = int(sys.stdin.readline().rstrip())
    a = [int(i) for i in sys.stdin.readline().split()]
    Adj = [[] for i in range(n)]

    for i in range(n - 1):
        u, v = map(int, sys.stdin.readline().split())
        u, v = u-1, v-1
        Adj[u].append(v)
        Adj[v].append(u)

    max_v = max(a)
    max_n = a.index(max_v)
    num_m = sum(ai == max_v for ai in a)

    if num_m == 1:
        ans = max_v

        rinsetu = [False] * n

        for u in Adj[max_n]:
            rinsetu[u] = True

        rinsetu[max_n] = True

        for u in range(n):
            if rinsetu[u]:
                continue
            if a[u] == max_v - 1:
                ans = max_v + 1
                break
    else:
        for u in range(n):
            cnt = 0

            if a[u] == max_v:
                cnt += 1

            for v in Adj[u]:
                if a[v] == max_v:
                    cnt += 1

            if cnt == num_m:
                ans = max_v + 1
                break
        else:
            ans = max_v + 2

    print(ans)


def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def __starting_point():
    solve()
__starting_point()

def main():
    n = int(input())
    a = list(map(int, input().split()))
    graph = [[] for _ in range(n)]
    for i in range(n - 1):
        u, v = [int(x) - 1 for x in input().split()]
        graph[u].append(v)
        graph[v].append(u)

    a_max = max(a)
    max_count_0 = sum(ai == a_max for ai in a)
    prev_count_0 = sum(ai == a_max - 1 for ai in a)

    result = a_max + 2
    for u in range(n):
        max_count = max_count_0
        prev_count = prev_count_0
        if a[u] == a_max:
            max_count -= 1
        else:
            prev_count -= 1

        for v in graph[u]:
            if a[v] == a_max:
                max_count -= 1
                prev_count += 1
            elif a[v] == a_max - 1:
                prev_count -= 1

        if max_count == 0:
            if prev_count == 0:
                result = a_max
                break
            else:
                result = a_max + 1

    print(result)


def __starting_point():
    # import sys
    # sys.stdin = open("C.txt")
    main()

__starting_point()


import random
n = int(input())
strengths = list(map(int,input().split()))
l = [[] for i in range(n)]
for j in range(n-1):
    a,b = list(map(int,input().split()))
    l[a-1].append(b-1)
    l[b-1].append(a-1)
hacked = max(strengths)
greatest_value = sum(i==hacked for i in strengths)
result = hacked
if greatest_value == 1:
    computer = strengths.index(result)
    adjlist = set(l[computer])
    adjlist.add(computer)
    for i in range(n):
        if i in adjlist:
            continue
        if strengths[i] == hacked - 1:
            result += 1
            break
else:
    for i in range(n):
        count = 0
        if strengths[i] == hacked:
            count += 1
        for v in l[i]:
            if strengths[v] == hacked:
                count += 1
        if count == greatest_value:
            result += 1
            break
    else:
        result += 2
print (result)



from collections import defaultdict, Counter

n = int(input())
a = list(int(v) for v in input().split()) + [-1000000002]
c = Counter(a)
#print(a, set(a), sorted(set(a)))
top, sec = sorted(set(a))[-1:-3:-1]
topC, secC = [0]*n, [0]*n
#print(top, c[top], sec, c[sec])
for i in range(n-1):
    u, v = (int(v) for v in input().split())
    if a[u-1] == top: topC[v-1] += 1
    if a[v-1] == top: topC[u-1] += 1
    if a[u-1] == sec: secC[v-1] += 1
    if a[v-1] == sec: secC[u-1] += 1

ans = top+2 # worst case
for i in range(n):
    # Process top numbers
    add = 1 if a[i] == top else 0 # haista vittu
    if topC[i]+add < c[top]: continue # there are tops beyond connected
    best = top+1 if topC[i] else top # sole top or tops connected
    # Second top can be nexus only if all tops are connected to it

    # Process second numbers
    add = 1 if a[i] == sec else 0 # haista vittu
    if secC[i]+add < c[sec]: best = max(best, sec+2) # seconds beyond
    # sec+1 <= top so we're done

    ans = min(ans, best)

print(ans)


from collections import Counter

n = int(input())
a = list(int(v) for v in input().split()) + [-1000000002]
c = Counter(a)

top, sec = sorted(set(a))[-1:-3:-1]
topC = [1 if v==top else 0 for v in a]
secC = [1 if v==sec else 0 for v in a]

#print(top, topC)
#print(sec, secC)

for i in range(n-1):
    u, v = (int(v) for v in input().split())
    if a[u-1] == top: topC[v-1] += 1
    if a[v-1] == top: topC[u-1] += 1
    if a[u-1] == sec: secC[v-1] += 1
    if a[v-1] == sec: secC[u-1] += 1

ans = top+2 # worst case
for i in range(n):
    if topC[i] < c[top]: continue # can only get top+2 here

    best = top if topC[i]==1 and a[i]==top else top+1 # sole top or else

    if secC[i] < c[sec]: best = max(best, sec+2) # seconds beyond

    ans = min(ans, best)

print(ans)