做法参考原论文。感谢 gblaasnicse 老师的指导。
设第一个排列第 $i$ 个位置要被移动到第二个排列的第 $a_i$ 个位置（$1\leq i,a_i\leq n$)。
交换相邻两个人会让前面人往右位移 $1$，后面人位移 $-1$。每个人安排 $x_i$，表示钦定的位移，则要求 $\sum x_i=0$ 且 $x_i\equiv a_i-i\pmod n$。
考虑每两点之间的贡献。设 $c_{i,j}=\lfloor\frac{i+x_i-j-x_j}{n}\rfloor-\lfloor\frac{i-j}{n}\rfloor$，则答案是：
$$\frac{1}{2}\sum_{1\leq i,j\leq n}|c_{i,j}|$$
三件事：
$x_i$ 不全为 $0$ 时，一定存在 $x_i>x_{i\bmod n+1}$，这时可以交换相邻的，答案会减小 $1$。
每次找一个 $x_i-x_j>n$ 的点对，调整为 $(x_i-n,x_j+n)$，有限步后 $x$ 的值域被定在了长度至多为 $n$ 的区间内。且这样的 $x$ 序列唯一。
对于极差大于 $n$ 的 $x$ 序列，一定存在一步调整，使得答案更小。
有了这三个结论后，做法就呼之欲出了。可以先进行 $O(n)$ 步调整最大最小值将 $x$ 的极差缩小，再用队列维护所有可能 $x_i>x_{i\bmod n+1}$ 的位置，$O(n^2)$ 次操作后即可排序。
下面简述下证明：
先明确如下几件事：
- $c_{i,j}+c_{j,i}=0$
- $x_i=\sum\limits_{j=1}^{n}c_{i,j}$
第一条显然，第二条稍微推下，注意 $\{\frac{i}{n}\}$ 和 $\{\frac{i+x_i}{n}\}$ 都构成完系：
$$\sum_{j=1}^{n}\Big(\lfloor\frac{i+x_i-j-x_j}{n}\rfloor-\lfloor\frac{i-j}{n}\rfloor\Big)$$
$$=\sum_{j=1}^{n}\Big(\frac{i+x_i-j-x_j}{n}-\frac{i-j}{n}+\Big\{\frac{i+x_i-j-x_j}{n}\Big\}-\Big\{\frac{i-j}{n}\Big\}\Big)$$
$$=\sum\limits_{j=1}^{n}\frac{x_i-x_j}{n}=x_i$$
回到三个结论。第二个比较好证，调整的时候 $x$ 排序后的字典序会增大。如果有两个合法序列 $x,x'$，设它们的最小最大值分别为 $L,R,L',R'$，不妨 $(L',-R')\geq (L,-R)$。那么一定有 $x'_i\geq x_i$，由总和限制得出两序列相同。
第一个结论：由对称性，不妨 $i=1$。$1,2$ 与其它人的贡献换了个遍，内部 $|c_{1,2}|$ 和 $|c_{2,1}|$ 互换并减小，因此步数刚好少一。
最难的是最后一个结论：
如果存在 $c_{i,j}\geq 2$，令 $x_i\leftarrow x_i-n,x_j\leftarrow x_j+n$ 一定更优。
否则，设 $x_i=\max{\{x_k\}},x_j=\min{\{x_k\}}$，做上面调整一定更优。
引理：$\forall i,j,k$，有 $c_{i,j}\leq c_{i,k}+c_{k,j}+1$。
这是因为 $\lfloor\frac{a+b}{n}\rfloor-\lfloor\frac{a}{n}\rfloor-\lfloor\frac{b}{n}\rfloor$ 只能为 $0,1$，$c_{i,j}$ 里面两个取整式符号相反，所以差值一定在 $-1$ 到 $1$ 之间。
那如果 $c_{i,j}\geq 2$，一定有 $c_{i,k}\geq 1$ 或者 $c_{k,j}\geq 1$，调整对 $k$ 影响非正。$c_{i,j}$ 会减 $2$，所以总和至少减了 $2$。
不然所有 $c_{i,j}\in \{-1,0,1\}$。设最大最小值点分别为 $a,b$，则 $c_{a,b}\geq 1$，内部贡献减了 $2$ 绝对值不变。
设 $P_i$ 为 $c_{i,j}(1\leq j\leq n)$ 中 $1$ 的个数，$N_i$ 为 $-1$ 的个数。则 $x_a=P_a-N_a,x_b=P_b-N_b$。
由 $x_a-x_b>n$，则 $P_a+N_b-N_a-P_b>n$，所以 $P_a+N_b>n$。
变化量至多为 $n-P_a-P_a+n-N_b-N_b=2(n-P_a-N_b)<0$，证毕。