N个整数组成的数组，定义子数组a[i]…a[j]的宽度为：max(a[i]…a[j]) - min(a[i]…a[j])，求所有子数组的宽度和。
输入
第1行：1个数N，表示数组的长度。(1 <= N <= 50000)
第2 - N + 1行：每行1个数，表示数组中的元素(1 <= A[i] <= 50000)
输出
输出所有子数组的宽度和。
输入样例
5
1
2
3
4
5
输出样例
20
使用单调栈处理出以a[i]为最小值和最大值的左右边界
答案为：sum : (i - Lmax[i]) * (Rmax[i] - i) * a[i] - (i - Lmin[i]) * (Rmin[i] - i) * a[i]

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int a[maxn];
int Lmin[maxn], Rmin[maxn];
int Lmax[maxn], Rmax[maxn];
stack<int> s;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	a[0] = 0; a[n + 1] = 0;
	for (int i = 1; i <= n + 1; i++) {
		while (!s.empty() && a[s.top()] >= a[i]) {
			Rmin[s.top()] = i;
			s.pop();
		}
		s.push(i);
	}
	while (!s.empty()) s.pop();
	for (int i = n; i >= 0; i--) {
		while (!s.empty() && a[s.top()] > a[i]) {
			Lmin[s.top()] = i;
			s.pop();
		}
		s.push(i);
	}
	a[0] = 1e9; a[n + 1] = 1e9;
	while (!s.empty()) s.pop();
	for (int i = 1; i <= n + 1; i++) {
		while (!s.empty() && a[s.top()] <= a[i]) {
			Rmax[s.top()] = i;
			s.pop();
		}
		s.push(i);
	}
	while (!s.empty()) s.pop();
	for (int i = n; i >= 0; i--) {
		while (!s.empty() && a[s.top()] < a[i]) {
			Lmax[s.top()] = i;
			s.pop();
		}
		s.push(i);
	}
	long long ans = 0;
	for (int i = 1; i <= n; i++) {
		ans += 1LL * (i - Lmax[i]) * (Rmax[i] - i) * a[i];
		ans -= 1LL * (i - Lmin[i]) * (Rmin[i] - i) * a[i];
	}
	cout << ans << endl;
	return 0;
}