if \(k=i\),we let the answer be like this: \(\dfrac{res}{i \times i}\).

\(res\) means that the total contribution before place \(i\).

Donominator can be solved easily,the only problem is how to find out \(res\).

Assuming that now we are at place \(i\),the total contribution before \(i-1\) is \(res\),so we can only calc the contribution on the place \(i\).

Let \(j\) be a position before \(i\).We could classified all situations:

1. \(a_j>a_i\),\(\ \ \max(a_i,a_j)=a_j\).

2. \(a_j \le a_i\),\(\ \ \max(a_i,a_j)=a_i\).

So we could easily calc \(res\) by Segment Tree or Bit.

Example Code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
int const mod=998244353;
int const N=2e5+10;int n,a[N];
inline int qpow(int a,int b){
    int ans=1;
    while (b){
        if (b&1) ans*=a,ans%=mod;
        a*=a,a%=mod;b>>=1;
    }
    return ans;
}
struct Tree_Array{
    int c[N];
    #define lowbit(x) (x&-x)
    inline void update(int x,int v){while (x<=N-10) c[x]+=v,c[x]%=mod,x+=lowbit(x);}
    inline int query(int x){int res=0;while (x) res+=c[x],x-=lowbit(x),res%=mod;return res;}
}T1,T2;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for (int i=1;i<=n;++i) cin>>a[i];
    int res=0;
    for (int i=1;i<=n;++i){
        res+=2*a[i]*(T1.query(a[i]))%mod;
        res%=mod;res+=a[i];res%=mod;
        res+=2*((T2.query(N-10)-T2.query(a[i]))%mod+mod)%mod;
        T2.update(a[i],a[i]);
        T1.update(a[i],1);res%=mod;res+=mod;res%=mod;
        cout<<res*qpow(i*i%mod,mod-2)%mod<<'\n';
    }
    return 0;
}