rt

#include<bits/stdc++.h>
#define INF 2e18
#define endl '\n'
#define PI acos(-1)
#define pb push_back
#define fi first
#define se second
#define int long long
#define mem(x,v) memset(x,v,sizeof x)
using namespace std;
const int N = 3e6+5;
const int V = 1e9;

int n,rt,tot;
int a[N],f[N],pre[N];
struct Tree{int ls,rs,siz;}t[N];
vector <int> g[N];

void pushup(int u){t[u].siz=t[t[u].ls].siz+t[t[u].rs].siz;}
void modify(int &u,int pos,int k,int tl,int tr){
	if(pos<tl||tr<pos)return;
	if(!u)u=++tot;
	if(tl==tr){t[u].siz+=k;return;}
	int mid=tl+tr>>1;
	modify(t[u].ls,pos,k,tl,mid);
	modify(t[u].rs,pos,k,mid+1,tr);
	pushup(u);
}
int rnk(int u,int k,int tl,int tr){
	if(tl==tr)return tl;
	int mid=tl+tr>>1;
	if(k<=t[t[u].ls].siz)return rnk(t[u].ls,k,tl,mid);
	else return rnk(t[u].rs,k-t[t[u].ls].siz,mid+1,tr);
}
void dfs1(int u,int fa){
	modify(rt,a[u],1,1,V);
	if(t[u].siz&1)pre[u]=rnk(rt,(t[rt].siz+1)/2,1,V);
	else pre[u]=(rnk(rt,t[rt].siz/2,1,V)+rnk(rt,t[rt].siz/2+1,1,V))/2;
	for(int v:g[u]){
		if(v==fa)continue;
		dfs1(v,u);
	}
	modify(rt,a[u],-1,1,V);
}
void dfs2(int u,int fa,int op){
	if(op==1)f[u]=INF;
	if(g[u].size()==1&&fa)f[u]=pre[u];
	for(int v:g[u]){
		if(v==fa)continue;
		dfs2(v,u,op^1);
		if(op==1)f[u]=min(f[u],f[v]);
		else f[u]=max(f[u],f[v]);
	}
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1,u,v;i<n;i++)cin>>u>>v,g[u].pb(v),g[v].pb(u);
	dfs1(1,0),dfs2(1,0,0),cout<<f[1];
	return 0;
}