#include #include using namespace std; using namespace atcoder; // using mint = modint1000000007; // const int mod = 1000000007; using mint = modint998244353; const int mod = 998244353; const int INF = 1e9; const long long LINF = 1e18; #define rep(i, n) for (int i = 0; i < (n); ++i) #define rep2(i, l, r) for (int i = (l); i < (r); ++i) #define rrep(i, n) for (int i = (n)-1; i >= 0; --i) #define rrep2(i, l, r) for (int i = (r)-1; i >= (l); --i) #define all(x) (x).begin(), (x).end() #define allR(x) (x).rbegin(), (x).rend() #define P pair template inline bool chmax(A& a, const B& b) { if (a < b) { a = b; return true; } return false; } template inline bool chmin(A& a, const B& b) { if (a > b) { a = b; return true; } return false; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; cin >> n; vectora(n); rep(i, n)cin >> a[i]; mint ans = 0; auto dfs = [&](auto&& dfs, int l, int r) { if (l + 1 == r) return; int m = (l + r) / 2; int lsz = m - l; int rsz = r - m; vector csmin1(rsz + 1); vector csmin2(rsz + 1); vector csmax1(rsz + 1); vector csmax2(rsz + 1); vector csmaxmin(rsz + 1); vectorcmin(rsz), cmax(rsz); { long long mn = INF, mx = -INF; rep(i, rsz) { chmin(mn, a[m + i]); chmax(mx, a[m + i]); cmin[i] = mn; cmax[i] = mx; csmin1[i + 1] += csmin1[i] + mn; csmin2[i + 1] += csmin2[i] + mn * mn; csmax1[i + 1] += csmax1[i] + mx; csmax2[i + 1] += csmax2[i] + mx * mx; csmaxmin[i + 1] += csmaxmin[i] + mn * mx; } } { long long mn = INF, mx = -INF; int rmax = 0, rmin = 0; rrep2(i, l, m) { chmin(mn, a[i]); chmax(mx, a[i]); while (rmin < rsz && mn < cmin[rmin]) rmin++; while (rmax < rsz && cmax[rmax] < mx) rmax++; // mx * mx ans += mint(mx) * mx * rmax; ans += csmax2[rsz] - csmax2[rmax]; // mn * mn ans += mint(mn) * mn * rmin; ans += csmin2[rsz] - csmin2[rmin]; // -2 * mn * mx ans -= mint(2) * mn * mx * min(rmax, rmin); if (rmax < rmin) { ans -= mint(2) * mn * (csmax1[rmin] - csmax1[rmax]); } else { ans -= mint(2) * (csmin1[rmax] - csmin1[rmin]) * mx; } ans -= mint(2) * (csmaxmin[rsz] - csmaxmin[max(rmax, rmin)]); } } dfs(dfs, l, m); dfs(dfs, m, r); }; dfs(dfs, 0, n); cout << ans.val() << endl; return 0; }