测试

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=3e5+2;
int n,t1,t2,a[N],f1[N],f2[N],g1[N],g2[N];LL S,ans;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
int main(){
    in(n);
    for(Re i=1;i<=n;++i)in(a[i]);
    f1[++t1]=a[1],f2[++t2]=a[1],g1[t1]=g2[t2]=1,ans=S=0;//初始化入队
    for(Re i=2;i<=n;++i){
        Re tmp=1;//f1[i]和f2[i]都一定会被覆盖，所以初始化为1
        while(t1&&f1[t1]<=a[i])S-=(LL)f1[t1]*g1[t1],tmp+=g1[t1--];//更新最大值
        f1[++t1]=a[i],g1[t1]=tmp,S+=(LL)a[i]*tmp;
        tmp=1;
        while(t2&&f2[t2]>=a[i])S+=(LL)f2[t2]*g2[t2],tmp+=g2[t2--];//更新最小值
        f2[++t2]=a[i],g2[t2]=tmp,S-=(LL)a[i]*tmp;
        ans+=S;//累加答案
    }
    printf("%lld\n",ans);
    return 0;
}
	Wpr