动态规划+排列组合=AC

#include<bits/stdc++.h>
using namespace std;
long long t,n,pos,a[1000005],dp[1000005][6],ans;
int main(){
	scanf("%lld%lld",&n,&a[1]),dp[1][1]=dp[1][3]=dp[n][2]=dp[n][4]=1;
	for(int i=2;i<=n;i++){
		scanf("%lld",&a[i]);
		if(a[i]>a[i-1]){
			pos=i-1;
			while(pos>0&&a[i]>a[pos]) pos-=dp[pos][1];
			dp[i][1]=i-pos;
		}else dp[i][1]=1;
		if(a[i]<a[i-1]){
			pos=i-1;
			while(pos>0&&a[i]<a[pos]) pos-=dp[pos][3];
			dp[i][3]=i-pos;
		}else dp[i][3]=1;
	}
	for(int i=n-1;i;i--){
		if(a[i]>=a[i+1]){
			pos=i+1;
			while(pos<=n&&a[i]>=a[pos]) pos+=dp[pos][2];
			dp[i][2]=pos-i;
		}else dp[i][2]=1;
		if(a[i]<=a[i+1]){
			pos=i+1;
			while(pos<=n&&a[i]<=a[pos]) pos+=dp[pos][4];
			dp[i][4]=pos-i;
		}else dp[i][4]=1;
	}
	for(int i=1;i<=n;i++) ans+=(dp[i][1]*dp[i][2]-dp[i][3]*dp[i][4])*a[i];
	printf("%lld",ans);
	return 0;
}