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