数据范围和时限来看的话感觉是勉强卡不过去，拆开交了几发，最后一个点大致是在1.5s。

瞪半天没什么能优化的点但是还是想发出来看看有没有神能帮忙调过

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define pii pair<int, int>
using namespace std;
const int MAX = 1e6 + 65;
const int mod = 998244353;
int sum[MAX << 2], lz[MAX << 2];
int sb[MAX], cnt[MAX];
int a[MAX], pre[MAX], suf[MAX];

void push(int l, int r, int p) ;
void fix(int l, int r, int s, int t, int p, int k) {
	if(s <= l && r <= t) {
		sum[p] = (r - l + 1) * (r + l) / 2 % mod * pre[k - 1] % mod;
		sum[p] = (sum[p] - (sb[r - 1] - sb[l - 1 - 1] + mod) % mod * k % mod) % mod;
		sum[p] = (sum[p] + (r - l + 1) * suf[k] % mod + mod) % mod;
		lz[p] = k;
		return ;
	}
	push(l, r, p);
	int mid = l + r >> 1;
	if(s <= mid) fix(l, mid, s, t, p * 2, k);
	if(mid < t) fix(mid + 1, r, s, t, p * 2 + 1, k);
	sum[p] = sum[p * 2] + sum[p * 2 + 1];
}
void push(int l, int r, int p) {
	if(lz[p]) {
		int mid = l + r >> 1;
		fix(l, mid, l, mid, p * 2, lz[p]);
		fix(mid + 1, r, mid + 1, r, p * 2 + 1, lz[p]);
		lz[p] = 0;
	}
}
int query(int l, int r, int s, int t, int p) {
	if(s <= l && r <= t) {
		return sum[p];
	}
	push(l, r, p);
	int mid = l + r >> 1, ans = 0;
	if(s <= mid) ans += query(l, mid, s, t, p * 2);
	if(mid < t) ans = (ans + query(mid + 1, r, s, t, p * 2 + 1)) % mod;
	return ans;
}

void run() {
	int n;
	cin >> n;
	int N = 0;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		N = max(N, a[i]);
		
		pre[i] = pre[i - 1] + a[i];
		pre[i] %= mod;
	}
	N += 3; 
	for(int i = n; i >= 1; i--) {
		suf[i] = suf[i + 1] + a[i];
		suf[i] %= mod; 
	}
	for(int i = 1; i <= N; i++) {
		sb[i] = (sb[i - 1] + i * i) % mod;
		cnt[i] = (cnt[i - 1] + i * (i - 1)) % mod;
	}
	
	fix(1, N, 1, N, 1, n + 1);
	int ans = 0;
	
	for(int i = n; i >= 1; i--) {
		int now = suf[i], qry = 0;
		qry = query(1, N, 2, a[i], 1);
		qry = (qry - (a[i] - 1) * (a[i] + 2) / 2 % mod * pre[i - 1] % mod + mod) % mod;
		qry = (qry - cnt[a[i]] + mod) % mod; 
		
		int j = 0;
		j = (j - sb[a[i] - 1] * (i + 1) % mod + mod) % mod; 
		qry = (qry - j % mod + mod) % mod;
		
		now = (now + qry) % mod;
		ans = (ans + now) % mod;
		fix(1, N, a[i] + 1, N, 1, i);
	}
	cout << ans << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t = 1;
//	cin >> t;
	while(t--) {
		run();
	}
	return 0;
}