求调 ABC F

#include <bits/stdc++.h>
using namespace std;
int MAXN=200000;
int n,p[200010],dp[200010];
int l[200010],r[200010];
int st[200010][20];
int logn[200010],pow2[20];
stack<int> s;
void pre(){
	logn[1]=0;
	logn[2]=1;
	for(int i=3;i<=n;i++){
		logn[i]=logn[i/2]+1;
	}
	pow2[0]=1;
	for(int i=1;i<=19;i++){
		pow2[i]=pow2[i-1]*2;
	}
}
int query(int l,int r){
	if(l==r) return l;
	int t=logn[r-l+1];
	int lc=st[l][t],rc=st[r-pow2[t]+1][t];
	if(p[lc]>p[rc]){
		return lc;
	}else{
		return rc;
	}
}
int getans(int l,int r){
	if(l==r) return 0;
	if(r-l==1) return abs(p[r]-p[l]);
	int ans=0;
	int maxx=query(l,r);
	if(maxx!=l){
		int maxl=query(l,maxx-1);
		ans=max(ans,getans(l,maxx-1)+abs(maxx-maxl));
	}
	if(maxx!=r){
		int maxr=query(maxx+1,r);
		ans=max(ans,getans(maxx+1,r)+abs(maxr-maxx));
	}
	return ans;
}
signed main(){
	//ios::sync_with_stdio(0);
	//cin.tie(0);
	//cout.tie(0);
	cin>>n;
	p[0]=1e9,p[n+1]=1e9;
	pre();
	for(int i=1;i<=n;i++){
		cin>>p[i];
	}
	for(int j=0;pow2[j]<=n;j++){
		for(int i=1;i<=n-pow2[j]+1;i++){
			if(j==0){
				st[i][j]=i;
			}else{
				int lc=st[i][j-1];
				int rc=st[i+pow2[j-1]][j-1];
				if(p[lc]>p[rc]){
					st[i][j]=lc;
				}else{
					st[i][j]=rc;
				}
			}
		}
	}
	s.push(n+1);
	for(int i=n;i>=1;i--){
		if(!s.empty()){
			while(!s.empty() && p[s.top()]<p[i]){
				s.pop();
			}
		}
		r[i]=s.top()-1;
		s.push(i);	
	}
	while(!s.empty()) s.pop();
	s.push(0);
	for(int i=1;i<=n;i++){
		if(!s.empty()){
			while(!s.empty() && p[s.top()]<p[i]){
				s.pop();
			}
		}
		l[i]=s.top()+1;
		s.push(i);
	}
	cout<<getans(1,n);
	return 0;
}
/*
8
2 6 4 8 7 1 5 3
*/