#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
const int N = 5e5+5;
const int INF = 1e9;
ll n,a[N],dp[N];
ll anser ;
ll s1[N],s2[N],w1[N],w2[N];
int t1,t2;
int main(){
cin >> n ;
for(int i = 1 ; i <= n ; i ++ ){
cin >> a[i];
dp[i] = dp[i-1];
ll sum = 0 ;
ll k = 0 ;
while(a[s1[t1]] < a[i] && t1){
k += w1[t1];
sum += (a[i] - a[s1[t1]]) * w1[t1] ;
t1 -- ;
}
s1[t1] = i ;
w1[t1] = 1 + k ;
dp[i] += sum ;
sum = 0 ; k = 0 ;
while(a[s2[t2]] > a[i] && t2){
k += w2[t2];
sum += (a[s2[t2]]-a[i]) * w2[t2];
t2-- ;
}
s2[ t2] = i;
w2[t2] = 1 + k;
dp[i] += sum;
anser += dp[i];
}
cout << anser << endl;
return 0;
}
[链接描述](
url