思路就是：穷举每个区间最小值，看这个最小值能影响多少个区间。再穷举每个区间的最大值，看这个最大值能影响多少个区间。所以我们就先用单调栈求最大最小值。

#include<bits/stdc++.h>
using namespace std;
int n;
int ans=0;
int top=1;
int st[1000001];
int a[1000001];
int led[1000001],lex[1000001],rid[1000001],rix[1000001];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    a[0]=int(1e9);
    for(int i=n;i>=1;i--){
        while(a[i]>=a[st[top]])top--;
        led[i]=st[top];
        top++;
        st[top]=i;
    }//左边第一个比它大的
    top=1;
    memset(st,0,sizeof(0));
    for(int i=1;i<=n;i++){
        while(a[i]>=a[st[top]])top++;
        rid[i]=st[top];
        top++;
        st[top]=i;
    }//右边第一个比它大的
    for(int i=1;i<=n;i++)ans+=(i-led[i])*(rid[i]-i);//乘法原理求贡献了多少
    top=1;
    memset(st,0,sizeof(0));
    for(int i=n;i>=1;i--){
        while(a[i]>=a[st[top]])top--;
        lex[i]=st[top];
        top++;
        st[top]=i;
    }//左边第一个比它小的
    top=1;
    memset(st,0,sizeof(0));
    for(int i=1;i<=n;i++){
        while(a[i]<=a[st[top]])top++;//这行有问题，不知道哪错了
        rix[i]=st[top];
        top++;
        st[top]=i;
    }//右边第一个比它小的
    for(int i=1;i<=n;i++)ans-=(i-lex[i])*(rix[i]-i);//乘法原理求贡献了多少
    cout<<ans<<endl;
    return 0;
}