CF396D

看到计算逆序对数量，毫无疑问是要分开算贡献的，但是怎么算是个问题。

先不考虑怎么算，先考虑怎么处理字典序小于 $p$ 这个条件方便。设一个字典序小于 $p$ 的排列为 $p'$，发现可以用和数位 dp 类似的方式，看最前面多少位是顶到上界的，再根据第一位没顶满的 $p_i'$ 的取值算贡献。

设当前枚举第一个位没顶满的是第 $i$ 位，此时发现已经可以将序列分成不同的几部分算贡献了：

• 第 $i$ 位与后面的数产生的贡献。

此时如果 $p_i'$ 在还没有确定的数中排名是 $x$，则排名 $<x$ 的数，一共 $x-1$ 个，一定都会出现在后面 $[i+1,n]$ 内，产生贡献。对于 $x$，产生的贡献即为 $(x-1)\times(n-i)!$。所以设原序列 $p_i$ 在还没确定的数中排名 $k$，这一部分贡献就是 $\sum_{j<k} (j-1)\times(n-i)!=\dfrac{(k-1)\times(k-2)}{2}\times(n-i)!$。

• 第 $i$ 位后面的数间产生的贡献。

此时可以将后面的数当成 $[1,n-i]$ 的一个排列来算。贡献是简单的，每两个数都有 $\dfrac{1}{2}$ 的情况为正序对，否则为逆序对。再乘上 $p_i'$ 的取值方案 $k-1$ 种，最后就有 $(k-1)\times\dfrac{(n-i)\times(n-i-1)}{2}\times\dfrac{(n-i)!}{2}$ 的贡献。

除此之外，当第 $i$ 位顶满时，也是有贡献的，设后面的数能组成 $<p$ 的排列数为 $c$ 个，则贡献为 $(k-1)\times c$。$c$ 需要用康托展开的方式求。需要 BIT 或者 SGT 维护。

code：

int n,m,a[N],f[N],fac[N];
il int Mod(int x,int y){return x+y>=mod?x+y-mod:x+y;}
struct BIT{
	int tr[N];
	#define lb(x) (x&(-x))
	il void upd(int x,int y){while(x<=n)tr[x]+=y,x+=lb(x);}
	il int qry(int x){int ret=0;while(x)ret+=tr[x],x-=lb(x);return ret;}
}T;
void Yorushika(){
	scanf("%d",&n);
	rep(i,1,n)scanf("%d",&a[i]);
	fac[0]=1;
	rep(i,1,n)fac[i]=1ll*fac[i-1]*i%mod;
	drep(i,n,1){
		f[i]=1ll*T.qry(a[i])*fac[n-i]%mod;
		T.upd(a[i],1);
		f[i]=Mod(f[i],f[i+1]);
	}
	const int iv=(mod+1)/2;
	int ans=0;
	rep(i,1,n){
		int p=T.qry(a[i]);
		ans=Mod(ans,(1ll*(p-2)*(p-1)/2)%mod*fac[n-i]%mod);
		ans=Mod(ans,(1ll*(n-i)*(n-i-1)/2)%mod*(p-1)%mod*fac[n-i]%mod*iv%mod);
		ans=Mod(ans,1ll*(p-1)*(f[i+1]+1)%mod);
		T.upd(a[i],-1);
	}
	printf("%d\n",ans);
}
signed main(){
	int t=1;
	//	scanf("%d",&t);
	while(t--)
		Yorushika();
}