分析

容易知道最多只需要 $3$ 次就可以完成排序，具体构造如下：

首先对前 $2n$ 个数排序，此时前 $n$ 大的数必定在后 $2n$ 个位置中；

然后对后 $2n$ 个数排序，此时前 $n$ 大的数已经完成了排序（在后 $n$ 个位置上且已经完成排序）。

最后再对前 $2n$ 个数排序，此时整个序列就完成了排序。

综上所述，至多只需要 $3$ 步就可以完成排序。

注意到一共有 $(3n)!$ 种情况，那么我们只需要分别求出操作次数 $=0$，操作次数 $\leq 1$，操作次数 $\leq 2$ 的情况数量即可。

操作次数 $=0$

即已经完成排序，只有 $1$ 种可能。

操作次数 $\leq 1$

只需要一次就能完成，那么必然要么前 $n$ 个数已经完成排序，要么后 $n$ 个数已经完成排序。

对于前 $n$ 个数已经完成排序，只需后 $2n$ 个数任意排列即可，方案数为 $(2n)!$。后 $n$ 个数已经完成排序同理。

注意两种情况可能重复，即前 $n$ 个数和后 $n$ 个数都已经完成排序，即中间 $n$ 个数任意排列，方案数为 $n!$。故答案为

$$2(2n)!-n!.$$

count1=2*fac[n<<1]-fac[n];

操作次数 $\leq 2$

操作次数为 $2$，要么是先操作前 $2n$ 个数，再操作后 $2n$ 个数，要么就两个操作交换。而这样能完成排序的充分必要条件是前 $n$ 小的数在前 $2n$ 个数中或者前 $n$ 大的数在后 $2n$ 个数中。

对于第一种情况，首先从前 $2n$ 个位置中选出 $n$ 个位置放前 $n$ 小的数，然后这 $n$ 个位置任意排序，其它 $2n$ 个位置任意排序即可。第二种情况也是如此，故方案数为

$$2\binom{2n}n(2n)!n!.$$

接着考虑两种情况的重复部分。枚举中间 $n$ 个位置中区间 $[2n+1,3n]$ 的数的个数 $i$，此时需要从这 $n$ 个位置中选出这 $i$ 个位置（$\dbinom ni$），再从后 $n$ 个位置中选出剩下 $n-i$ 个位置（$\dbinom n{n-i}$），最后再从前 $2n$ 个位置剩下的位置（共 $2n-i$ 个）中选出 $n$ 个位置（$\dbinom{2n-i}n$）即可。

count2=2*C(n<<1,n)*fac[n]%mod*fac[n<<1]%mod;
long long tmp=fac[n]*fac[n]%mod*fac[n]%mod;
// 2n+1 ~ 3n 中有 i 个在 [n+1, 2n] 上
for(int i=0;i<=n;i++)
    count2-=tmp*C(n,i)%mod*C(n,n-i)%mod*C(2*n-i,n)%mod;

总结

记求得的操作次数 $=0$，操作次数 $\leq 1$，操作次数 $\leq 2$ 的情况数量以及情况总数分别为 $c_0,\ c_1,\ c_2,\ c_3$，那么容易知道答案为

$$0\times c_0+1\times(c_1-c_0)+2\times(c_2-c_1)+3\times(c_3-c_2). $$

时间复杂度 $\Theta(n)$。

// 2023.05.31

#include<bits/stdc++.h>
using namespace std;
long long mod;
long long power(long long a,long long n=mod-2){
    long long res=1;
    while(n){
        if(n&1)res=res*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return res;
}
long long fac[3000001],invfac[3000001];
void initfac(int N){
    fac[0]=1;
    for(int i=1;i<=N;i++)
        fac[i]=fac[i-1]*i%mod;
    invfac[N]=power(fac[N]);
    for(int i=N;i>=1;i--)
        invfac[i-1]=invfac[i]*i%mod;
}
long long C(int m,int n){
    if(n<0||m<0||n>m)return 0;
    return fac[m]*invfac[n]%mod*invfac[m-n]%mod;
}

int main(){
    int n;
    scanf("%d%lld",&n,&mod);
    initfac(n*3);
    long long count0=1,
        count1=2*fac[n<<1]-fac[n],
        count2=2*C(n<<1,n)*fac[n]%mod*fac[n<<1]%mod,
        count3=fac[n*3];
    long long tmp=fac[n]*fac[n]%mod*fac[n]%mod;
    // 2n+1 ~ 3n 中有 i 个在 [n+1, 2n] 上
    for(int i=0;i<=n;i++)
        count2-=tmp*C(n,i)%mod*C(n,n-i)%mod*C(2*n-i,n)%mod;
    long long answer=1*(count1-count0)+2*(count2-count1)+3*(count3-count2);
    printf("%lld\n",(answer%mod+mod)%mod);
    return 0;
}