方法一：差分约束

#include<bits/stdc++.h>
#define k e[i].to
using namespace std;
int n,a[20001]={0},dis[20001]={0},home[20001]={0},cnt=0,ans=0;
struct node{
	int next,to;
}e[40001];
void putin(int a,int b){
	e[++cnt].to=b;
	e[cnt].next=home[a];
	home[a]=cnt;
}
void Dijkstra(){
	priority_queue<pair<int,int>,vector<pair<int,int> >,less<pair<int,int> > > q;
	q.push(make_pair(0,0));
	while(!q.empty()){
		int cnt=q.top().second;
		q.pop();
		for(int i=home[cnt];i;i=e[i].next){
			if(dis[k]<dis[cnt]+1){
				dis[k]=dis[cnt]+1;
				q.push(make_pair(dis[k],k));
			}
		}
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(i>1){
			if(a[i]>a[i-1]) putin(i-1,i);
			if(a[i-1]>a[i]) putin(i,i-1);
		}
	}
	for(int i=1;i<=n;i++) putin(0,i);
	Dijkstra();
	for(int i=1;i<=n;i++){
		ans+=dis[i];
	}
	printf("%d",ans);
	return 0;
}

方法二：拓扑排序

#include<bits/stdc++.h>
using namespace std;
int n,a[20001]={0},r[20001]={0},b[20001]={0},zhe[20001]={0},ans=0,now=1,cc=1;
queue<int> q;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<n;i++){
        if(a[i]>a[i+1]) r[i]++;
        else if(a[i]<a[i+1]) r[i+1]++;
    }
    for(int i=1;i<=n;i++) if(r[i]==0) q.push(i);
    while(!q.empty()){
        int cnt=q.front();
        q.pop();
        b[cc]=cnt;
        cc++;
        if(a[cnt]<a[cnt+1]&&cnt<n){
            r[cnt+1]--;
            if(r[cnt+1]==0) q.push(cnt+1);
        }
        if(a[cnt]<a[cnt-1]&&cnt>1){
            r[cnt-1]--;
            if(r[cnt-1]==0) q.push(cnt-1);
        }
    }
    for(int i=1;i<=n;i++){
        if(a[b[i]]>a[b[i]+1]&&zhe[b[i]+1]!=0){
            now=max(now,zhe[b[i]+1]+1);
        }
        if(a[b[i]]>a[b[i]-1]&&zhe[b[i]-1]!=0){
            now=max(now,zhe[b[i]-1]+1);
        }
        zhe[b[i]]=now;
    }
    for(int i=1;i<=n;i++) ans+=zhe[i];
    printf("%d",ans);
    return 0;
}