两个序列是同等地位的，假装第一步操作 $a$，然后你接下来必须操作 $b$ 不然无法得到新的结果，再下一次你只能操作 $a$，然后你发现你不能操作出新结果了。

于是你能得到的是按照 $(a_i,i),(b_i,a_i,i),(a_i,b_i,i)$ 三种权值排序出来的三个序列，你要做的是对所有可能的 $n^(2n)$ 种 $a,b$ 计数得到的不同的序列三元组数，然后除以 $n^(2n)$。

看起来很难做，先做小情况也就是 $n=2$，或者你可以参照一下样例解释，发现只有第一个序列是 $1,2$ 而第二个序列是 $2,1$ 时你会参照第三个序列区分开 $a_1=a_2$ 还是 $a_1< a_2$，而且其实如果你不能得知这个信息的话恰好只有 $(n!)^2$ 种，因为 $a,b$ 均为排列的情况两两不等。

记三个序列分别为 $p,q,r$。

也就是你只能多得到一些等号，具体来说是一个区间内全相等，这个区间在 $p$ 和 $r$ 上元素构成一致，要求在 $p$ 上升序，$r$ 上顺序与这些元素在 $q$ 的顺序一致上，而且不能切分成多个小的符合条件区间（不然说明这个等号没跨过去）。

所以你直接解下

$$ \frac{1}{1-F(x)}=\sum_{i=0}^{+\infty}i!x^i $$

然后给每个第 $i$ 项除以 $(i!)^2$ 后得到 $G(x)$，$\left(\frac{n!}{n^n}\right)^2[x^n]G(x)$ 即为答案。

具体来说你平移下下标变成 $1,2\cdots,k$，然后认为在 $p$ 上恰好是 $p_i=i$，再相应地动一下 $r$ 上的位置，然后你发现因为你切两个位置之间是独立的，所以你有唯一的划分成若干个极小的满足条件的区间，于是任何一个这样的序列恰好和所有极小序列顺序接起来（因为要求在 $p$ 上递增所以你简单平移下就好了）是双射的，就得到了这个生成函数方程，解一下即可，然后不同的极小区间之间我们没有任何限制，你需要为每个元素分配一下在 $p$ 和在 $q$ 上的下标（$r$ 直接由之决定），每个区间内要求是这两个顺序确定，所以你就是 $\left(\frac{n!}{\prod_i l_i}\right)^2$ 种分配方法，$l_i$ 是第 $i$ 个区间长度，写出来就是这样。