注意到上下两个序列的极差始终相同，因此只需要考虑第一个序列的极差即可。

考虑先求出 $1,n$ 的可能位置 $p,q$，考虑对下标编号进行二进制分组，每次将 $2^i$ 这一位为 $1$ 的下标交换下去，由于 $p \neq q$，因此一定有一位交换过后满足 $p,q$ 上面从两个 $1/n$ 变为 $1,n$ 或从 $1,n$ 变为两个 $1/n$，那么两个数字所在的集合不同，容易二分求出 $p,q$ 这两个位置是什么。

然后我们使得第一个序列的 $a_p,a_q$ 相同，重复前面的操作，之后不交换 $a_p,a_q$，按照前面的方式求出 $2,n-1$ 的位置 $p',q'$ 即可。

那么每个数字都需要 $2 \log n$ 次操作，考虑到你随机标号后一个二进制位每个位期望有 $\frac{1}{2}$ 的概率不同，因此期望操作次数为 $n \log n + 2n$ 次，实测远远达不到这个上界，可以通过此题。