Untitled

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;
}```