#include <bits/stdc++.h> #define L(i, j, k) for(int i = (j); i <= (k); i++) #define R(i, j, k) for(int i = (j); i >= (k); i--) #define ll long long #define sz(a) ((int) a.size()) #define all(a) a.begin(), a.end() #define vi vector<ll> #define pb emplace_back #define me(a, x) memset(a, x, sizeof(a)) #define fst first #define snd second #define ii pair<int, int> using namespace std; const int LOG=18; const int MAXN=2e5+5; ll p[MAXN],a[MAXN],b[MAXN],dp[MAXN],n; vector<ii> st; void upd(int k,ii val){ k+=n; st[k]=val; while(k/=2){ st[k]=max(st[k*2],st[k*2+1]); } } int que(int l,int r){ l+=n,r+=n; ii ans={-1,0}; while(l<r){ if(l&1)ans=max(ans,st[l++]); if(r&1)ans=max(ans,st[--r]); l/=2,r/=2; } return ans.snd; } ll f(int l,int r){ int m=que(l,r+1); ll l_=que(l,m),r_=que(m+1,r+1); ll ans=0; if(m!=l)ans=f(l,m-1)+abs(l_-m); if(m!=r)ans=max(ans,f(m+1,r)+abs(r_-m)); return ans; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cin>>n; st.resize(n*2,ii{-1,0}); L(i,0,n-1){ cin>>p[i]; upd(i,{p[i],i}); } L(i,0,n-2){ cin>>a[i]>>b[i]; } cout<<f(0,n-1)<<endl; }