[51nod 1215] array width

N An array of integers , Define subarray a[i]…a[j] The width is ：max(a[i]…a[j]) - min(a[i]…a[j]), Find the width sum of all subarrays .
Ideas ：
Maintain two monotonous stacks , Cumulative maximum * The interval length covered by the maximum value maxsum and Minimum and minimum Fuhai interval length minsum maxsum-minsum That's the answer.
Code ：

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
const int maxn=50010;
typedef long long ll;
int a1[maxn],a2[maxn];
int maxid[maxn],minid[maxn];
int id1,id2;
int n;
ll maxx,minn;
int main()
{
    
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",a1+i),a2[i]=a1[i];
    n++;
    a1[n]=0x7fffffff,a2[n]=-1;
    for(int i=1;i<=n;i++){
    
        while(id1&&a1[i]>=a1[maxid[id1]]) maxx+=1LL*a1[maxid[id1]]*ll(i-maxid[id1])*(maxid[id1]-maxid[id1-1]),id1--;
        while(id2&&a2[i]<=a2[minid[id2]]) minn+=1LL*a2[minid[id2]]*ll(i-minid[id2])*(minid[id2]-minid[id2-1]),id2--;
        minid[++id2]=maxid[++id1]=i;
        }
    printf("%lld",maxx-minn);
}