#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define fi first
#define se second
#define sza(a) (int)a.size()
#define pir pair<int,int>
#define pirll pair<ll,ll>
using namespace std;
const int maxn = 2e5 + 5;
vector <vector<int>> vec(maxn);
int a[maxn];
int input(int n){
int root = 0;
for (int i = 1 ; i <= n ; i++){
cin >> a[i];
if (a[i] == n) root = i;
}
for (int i = 1 ; i < n ; i++){
int u,v;
cin >> u >> v;
vec[u].push_back(v);
vec[v].push_back(u);
}
return root;
}
namespace sub_1_2_3_4{
bool check(int n){
return (n <= 5000);
}
const int N = 5090;
int node[N],dp[N];
int dfs(int u,int par,int len,int cap){
int res = dp[u] + len;
for (int v : vec[u])
if (v != par && a[v] < cap)
res = max(res,dfs(v,u,len + 1,cap));
return res;
}
ll solve(int n,int root){
for (int i = 1 ; i <= n ; i++)
node[a[i]] = i;
for (int i = 1 ; i <= n ; i++)
dp[node[i]] = dfs(node[i],node[i],0,i);
return dp[root];
}
}
namespace sub5{
const ll inf = 1e17;
struct segment_tree{
ll seg[4*maxn];
void init(int l,int r,int v){
seg[v] = -inf;
if (l == r) return;
int w = (l + r)/2;
init(l,w,2*v + 1);
init(w + 1,r,2*v + 2);
}
void update(int l,int r,int v,int p,ll val){
if (l > p || r < p) return;
if (l == r){
seg[v] = val;
return;
}
int w = (l + r)/2;
update(l,w,2*v + 1,p,val);
update(w + 1,r,2*v + 2,p,val);
seg[v] = max(seg[2*v + 1],seg[2*v + 2]);
}
ll calc(int l,int r,int v,int lx,int rx){
if (l > rx || r < lx) return -inf;
if (l >= lx && r <= rx) return seg[v];
int w = (l + r)/2;
return max(calc(l,w,2*v + 1,lx,rx),calc(w + 1,r,2*v + 2,lx,rx));
}
};
segment_tree U,D;
int node[maxn],nxt[maxn],lst[maxn];
ll dp[maxn];
void prepare(int n){
U.init(1,n,0);
D.init(1,n,0);
for (int i = 1 ; i <= n ; i++){
nxt[i] = n + 1;
node[a[i]] = i;
}
U.update(1,n,0,node[1],node[1]);
D.update(1,n,0,node[1],-node[1]);
deque <int> dq;
for (int i = 1 ; i <= n ; i++){
while (dq.size() && a[dq.back()] < a[i]) dq.pop_back();
lst[i] = (!dq.size()) ? 1 : (dq.back() + 1);
dq.push_back(i);
}
dq.clear();
for (int i = n ; i > 0 ; i--){
while (dq.size() && a[dq.back()] < a[i]) dq.pop_back();
nxt[i] = (!dq.size()) ? n : (dq.back() - 1);
dq.push_back(i);
}
}
ll solve(int n,int root){
prepare(n);
ll res = 0;
for (int i = 2 ; i <= n ; i++){
int p = node[i];
ll v = max(U.calc(1,n,0,p,nxt[p]) - p,D.calc(1,n,0,lst[p],p) + p);
v = max(v,0LL);
U.update(1,n,0,p,v + p);
D.update(1,n,0,p,v - p);
res = max(res,v);
}
return res;
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
// freopen("CAT.inp","r",stdin);
// freopen("CAT.out","w",stdout);
int n;
cin >> n;
int root = input(n);
if (sub_1_2_3_4::check(n)){
cout << sub_1_2_3_4::solve(n,root);
return 0;
}
cout << sub5::solve(n,root);
return 0;
}
