Untitled

mail@pastecode.io avatar
unknown
c_cpp
a year ago
2.0 kB
2
Indexable
Never
#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x...)
#endif

constexpr int MOD = 998244353;

void md(long long &n) {
    n = (n % MOD + MOD) % MOD;
}

void solve() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (long long &i : a) cin >> i;
    vector<long long> dmx(n + 1), dmn(n + 1), pdp(n + 2);
    dmx[0] = 1;
    dmn[0] = 0;
    pdp[1] = 1;
    vector<pair<int, int>> mx, mn;
    mx.emplace_back(INT_MAX, 0);
    mn.emplace_back(INT_MIN, 0);
    for (int i = 1; i <= n; i++) {
        while (a[i - 1] >= mx.back().first) {
            mx.pop_back();
        }
        debug(mx);
        for (int j = i - 1; j >= mx.back().second; j--) {
            debug(j, dmx[j] - dmn[j], a[i - 1]);
            dmx[i] += (dmx[j] - dmn[j]) * a[i - 1];
            md(dmx[i]);
        }
        for (int j = mx.size() - 1; j >= 1; j--) {
            debug(j);
            for (int c = mx[j - 1].second; c < mx[j].second; c++) {
                debug(c);
                dmx[i] += (dmx[c] - dmn[c]) * mx[j].first;
                md(dmx[i]);
            }
        }
        mx.emplace_back(a[i - 1], i);
        while (a[i - 1] <= mn.back().first) {
            mn.pop_back();
        }
        for (int j = i - 1; j >= mn.back().second; j--) {
            dmn[i] += (dmx[j] - dmn[j]) * a[i - 1];
            md(dmn[i]);
        }
        for (int j = mn.size() - 1; j >= 1; j--) {
            for (int c = mn[j - 1].second; c < mn[j].second; c++) {
                dmn[i] += (dmx[c] - dmn[c]) * mn[j].first;
                md(dmn[i]);
            }
        }
        mn.emplace_back(a[i - 1], i);
    }
    debug(dmx);
    debug(dmn);
    long long ans = dmx[n] - dmn[n];
    md(ans);
    cout << ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tests = 1;
    // cin >> tests;
    while (tests--) {
        solve();
    }
    return 0;
}