• 我们可以先计算每个子数组的最大值之和
• 再减去每个子数组的最小值之和
• 而子数组的最小值之和就是 LS1244. 【普及】子数组的最小值之和
• 子数组的最大值之和，只需要把数组取反，再重复一次就好
• 下面的代码：先求子数组的最大值之和，再将数组取反

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
const int P = 998244353;

int solveMax(const vector<int>& a) {
    int n = a.size();

    // L(i): 左边第一个 >= a[i] 的数的下标 
    vector<int> L(n, -1);

    // R(i): 右边第一个 > a[i] 的数的下标
    vector<int> R(n, n);

    vector<int> s(n);
    int e = 0;  // s 中元素的个数

    for (int i = 0; i < n; i++) {
        // 在 st 里从后往前找到第一个 >= a[i]
        // 出栈的时候确定右边第一个 > a[s[e - 1]] 的就是 a[i]
        while (e > 0 && a[s[e - 1]] < a[i]) R[s[--e]] = i;

        // 入栈的时候确定左边第一个 >= a[i] 的
        if (e != 0) L[i] = s[e - 1];
        s[e++] = i;
    }

    i64 ans = 0;
    for (int i = 0; i < n; i++) {
        ans = (ans + (i64) (i - L[i]) * (R[i] - i) * a[i]) % P;
    }
    return (ans + P) % P;
}

int main() {	
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    // 全部取反后计算最大值的贡献, 就是原数组最小值的贡献
    vector<int> b(n);
    for (int i = 0; i < n; i++) b[i] = -a[i];

    cout << (solveMax(a) + solveMax(b)) % P << '\n';

    return 0;
}