#include<bits/stdc++.h>
using namespace std;
#define S second
#define F first
#define ll long long
//#define int long long
//#pragma GCC optimize("Ofast, unroll-loop")
//#pragma GCC target("avx,avx2")
#pragma GCC optimize("O3")
const int inf=0x3f3f3f3f;
const ll inff=0x3f3f3f3f3f3f3f3f;
const int X=1000000007;
int p[200005], n, L[200005], R[200005];
ll seg[2][800005], ans;
#define m (l+r>>1)
#define L (id<<1)
#define R (id<<1|1)
void modify(int t, int pos, ll val, int l=0, int r=n, int id=1){
//cout << "modify" << val << '\n';
if(pos==l&&r==l+1){
seg[t][id]=max(seg[t][id],val);
return;
}
if(pos>=r||pos<l) return;
modify(t,pos,val,l,m,L), modify(t,pos,val,m,r,R);
seg[t][id]=max(seg[t][L],seg[t][R]);
}
ll query(int t, int ql, int qr, int l=0, int r=n, int id=1){
//cout << "que" << ql << ' ' << qr << '\n';
if(qr>=r&&ql<=l) return seg[t][id];
if(qr<=l||ql>=r) return 0;
return max(query(t,ql,qr,l,m,L),query(t,ql,qr,m,r,R));
}
#undef m
#undef L
#undef R
void init(){
stack<int> stk;
stk.push(-1);
for(int i=0 ; i<n ; i++){
while(stk.top()!=-1&&p[stk.top()]<p[i]) stk.pop();
L[i]=stk.top();
stk.push(i);
}
stack<int> stk2;
stk2.push(n);
for(int i=n-1 ; i>=0 ; i--){
while(stk2.top()!=n&&p[stk2.top()]<p[i]) stk2.pop();
R[i]=stk2.top();
stk2.push(i);
}
/*
for(int i=0 ; i<n ; i++) cout << L[i] << ' ';
cout << '\n';
for(int i=0 ; i<n ; i++) cout << R[i] << ' ';
cout << '\n';
*/
return;
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0);
memset(seg,0,sizeof seg);
cin >> n;
for(int i=0 ; i<n ; i++) cin >> p[i];
init();
for(int i=1 ; i<n ; i++){
int a, b; cin >> a >> b;
}
vector<int> v;
for(int i=0 ; i<n ; i++) v.push_back(i);
sort(v.begin(),v.end(),[&](int a, int b){
return p[a]<p[b];
});
for(int i:v){
ll temp=max(query(0,i+1,R[i])-i,query(1,L[i]+1,i)-(n-i));
temp=max(0LL,temp);
ans=max(ans,temp);
modify(0,i,temp+i);
modify(1,i,temp+(n-i));
//cout << i << ' ' << temp << '\n';
}
cout << ans << '\n';
return 0;
}
void test(){
string ss; cin >> ss;
int n=ss.size();
ss='.'+ss;
while(1){
int t; cin >> t;
string s=ss;
s[t]='R';
while(t>=1&&t<=n){
for(int i=1 ; i<=n ; i++){
if(i==t) cout << '(';
cout << s[i];
if(i==t) cout << ')';
}
cout << '\n';
if(s[t]=='R') s[t]='B', t++;
else s[t]='R', t--;
}
}
}
