分析

容易知道最多只需要 $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)$。