玄关

#include <iostream>
#include <stack>
#define N 300005

using namespace std;

int n;
long long a[N];
long long l[N], r[N], l1[N], r1[N];
long long ans;
stack< int > s, s1;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n + 1; i++) {
        while (!s.empty() && a[s.top()] >= a[i]) {
            r[s.top()] = i - 1;
            s.pop();
        }
        s.push(i);
        if (i == n + 1) {
            a[i] = 1000000001;
        }
        while (!s1.empty() && a[s1.top()] <= a[i]) {
            r1[s1.top()] = i - 1;
            s1.pop();
        }
        s1.push(i);
    }
    s.pop();
    s1.pop();
    for (int i = n; i >= 0; i--) {
        while (!s.empty() && a[s.top()] >= a[i]) {
            l[s.top()] = i + 1;
            s.pop();
        }
        s.push(i);
        if (i == 0) {
            a[i] = 1000000001;
        }
        while (!s1.empty() && a[s1.top()] <= a[i]) {
            l1[s1.top()] = i + 1;
            s1.pop();
        }
        s1.push(i);
    }
    s.pop();
    s1.pop();
    for (int i = 1; i <= n; i++) {
        // cout << l[i] << " " << r[i] << endl;
        // cout << l1[i] << " " << r1[i] << endl;
        ans += a[i] * (i - l1[i] + 1) * (r1[i] - i + 1);
        ans -= a[i] * (i - l[i] + 1) * (r[i] - i + 1);
    }
    cout << ans;
    return 0;
}