Untitled

mail@pastecode.io avatar
unknown
c_cpp
a year ago
1.9 kB
3
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<int> a(n);
    for (int &i : a) cin >> i;
    vector<long long> dmx(n + 1), dmn(n + 1), pdp(n + 2), precalcmx(n + 1), precalcmn(n + 1);
    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();
        }
        dmx[i] += (pdp[i] - pdp[mx.back().second]) * a[i - 1];
        md(dmx[i]);
        dmx[i] += precalcmx[mx.back().second];
        md(dmx[i]);
        mx.emplace_back(a[i - 1], i);
        precalcmx[i] = precalcmx[mx[mx.size() - 2].second] + (pdp[mx[mx.size() - 1].second] - pdp[mx[mx.size() - 2].second]) * mx[mx.size() - 1].first;
        md(precalcmx[i]);
        while (a[i - 1] <= mn.back().first) {
            mn.pop_back();
        }
        dmn[i] += (pdp[i] - pdp[mn.back().second]) * a[i - 1];
        md(dmn[i]);
        dmn[i] += precalcmn[mn.back().second];
        md(dmn[i]);
        mn.emplace_back(a[i - 1], i);
        precalcmn[i] = precalcmn[mn[mn.size() - 2].second] + (pdp[mn[mn.size() - 1].second] - pdp[mn[mn.size() - 2].second]) * mn[mn.size() - 1].first;
        md(precalcmn[i]);
        pdp[i + 1] = pdp[i] + (dmx[i] - dmn[i]);
        md(pdp[i + 1]);
    }
    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;
}