代码

#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;

#define lg long long
#define MN 1200005
#define lsk 998244353
#define lb(x) ((x)&(-(x)))

int n;
int a[MN>>1],c[MN>>1],D[MN>>1];

int read(){
	static int d;static char c;
	for(d=0,c=getchar();c<'0'||c>'9';c=getchar());
	for(;c>='0'&&c<='9';d=(d<<3)+(d<<1)+c-'0',c=getchar());
	return d;
}

void add(int x,int y){
	for(;x<=n;x+=lb(x))c[x]+=y;
}

int qry(int x){
	int res=0;
	for(;x;x-=lb(x))res+=c[x];
	return res;
}

lg fac[MN],ifac[MN];

lg Pow(lg A,lg B){
	lg res=1;
	for(;B;B>>=1,A=A*A%lsk)if(B&1)res=res*A%lsk;
	return res;
}

void init(){
	fac[0]=ifac[0]=1;
	for(int i=1;i<MN;++i){
		fac[i]=fac[i-1]*i%lsk;
		ifac[i]=Pow(fac[i],lsk-2);
	}
}

lg C(int A,int B){
	return fac[A]*ifac[B]%lsk*ifac[A-B]%lsk;
}

lg Q(int A,int B){
	return C(A,(A+B)/2);
}

lg T(int A,int B){
	if(B<0)return 0;
	return ((Q(A,B)-Q(A,B+2))%lsk+lsk)%lsk;
}

int main(){
	int TT;init();
	scanf("%d",&TT);
	while(TT--){
		memset(D,0,sizeof D);
		memset(c,0,sizeof c);
		scanf("%d",&n);lg res=0;
		for(int i=1;i<=n;++i)add(i,1);
		for(int i=1;i<=n;++i)a[i]=read();
		int mx=0,mn=1;
		for(int i=1;i<n;++i){
			int g=max(mx,a[i]);
			int f=qry(g)+1;
			int d=n*2-(i-1)*2-f;
			res=(res+T(d,f))%lsk;
			D[a[i]]=1;add(a[i],-1);
			if(a[i]>mx)mx=a[i];
			else{
			    if(a[i]!=mn)break;
			}
			while(D[mn])++mn;
		}
		printf("%lld\n",res);
	}
	return 0;
}

评测结果