The first step

For a fixed \(K\), there are \(K\) choices for each draw, for a total of \(K^2\) choices, so the desired value is \( \frac{\sum\limits_{i=1}^K\sum\limits_{j=1}^K\operatorname{​max}(A_i​,A_j​)}{K^2}\). Since \(K^2\) can be computed easily, we consider how to find \(\sum\limits_{i=1}^K\sum\limits_{j=1}^K​\operatorname{max}(A_i​,A_j​)\).

If we sort \(A_1,A_2,\dots,A_K\) in increasing order, the contribution of \(A_i\) to the answer of \(K\) is \(A_i\times(i\times2-1)\).

Why? Consider how many situations are there. If we choose \(A_i\) in the first chance, in the second chance let we choose \(A_j\), the \(\operatorname{max}\) will result in \(A_i\) if \(j\leq i\). So there will be \(i\) situations. If we choose \(A_i\) in the second chance, there will be another \(i\) situations. However, if we choose \(A_i\) twice, it will be counted twice. So \(-1\).

The second step

Since it is troublesome to compute for every \(K\), we will try to reuse the value for \(K−1\).

Consider how much the answer will change after adding \(A_K\).(this \(A\) isn’t sorted)

• If we know the rank of \(A_K\) in \(A_1,A_2,\cdots,A_K\), we can calculate the contribution of \(A_K\)：\(A_K\times (rank\times2-1)\).
• If we add \(A_K\) into the set of numbers of \(A_1,A_2,\cdots,A_{K-1}\), the ranks of numbers \(> A_K\) will \(+=1\). Contribution： \(2\times\) the sum of numbers \(\geq A_K\).

We need a datastructure that can support:

• insert a number \(A_K\).
• query the number of numbers \(\leq A_K\).
• query the sum of numbers \(> A_K\).

Splay is suitable for this task. It very easy to write it.

\(A_i\leq 2\times 10^5\) constraint is not used at all.

code

#include<stdio.h>
#define mod 998244353
#define int long long
inline int ksm(int a,int b)//pow
{
	int ans=1;
	for(;b;b>>=1,a*=a,a%=mod)if(b&1)ans*=a,ans%=mod;
	return ans;
}
struct node
{
	int x,sz,s;node*l,*r;
	inline node(const int&o){x=o;sz=1;s=o;l=r=0;}
}*rt;
inline void upd(node*i)
{
	i->sz=1;i->s=i->x;
	if(i->l)i->sz+=i->l->sz,i->s+=i->l->s;
	if(i->r)i->sz+=i->r->sz,i->s+=i->r->s;
}
inline node*L(node*i){node*j=i->r;i->r=j->l;j->l=i;upd(i);upd(j);return j;}
inline node*R(node*i){node*j=i->l;i->l=j->r;j->r=i;upd(i);upd(j);return j;}
inline char islay(node*&i,const int&x)
{
	if(!i)return i=new node(x),0;
	if(x<i->x)
	{
		char tmp=islay(i->l,x);
		if(tmp&1){i=R(i);i=R(i);return 0;}
		if(tmp&2){i->l=L(i->l);i=R(i);return 0;}
		return 1;
	}
	char tmp=islay(i->r,x);
	if(tmp&2){i=L(i);i=L(i);return 0;}
	if(tmp&1){i->r=R(i->r);i=L(i);return 0;}
	return 2;
}
inline void isplay(node*&i,const int&x)
{
	char tmp=islay(i,x);
	if(tmp&1)i=R(i);
	if(tmp&2)i=L(i);
}
main()
{
	int n,a,b,s=0;scanf("%lld",&n);
	for(int i=1;i<=n;++i)
	{
		scanf("%lld",&a);isplay(rt,a);
		b=rt->l?rt->l->sz:0;++b;
		s+=a*((b<<1)-1);
		b=rt->r?rt->r->s:0;
		s+=b<<1;
		printf("%lld\n",s%mod*ksm(i*i%mod,mod-2)%mod);
	}
}