感觉正常 OI 学生很难在不依赖大脑随机性情况下想出这道题，因为我们没有学斯特林公式。
考虑观察操作的影响，并确定还原策略。这道题中我们可以考虑按 \(1\rightarrow n\) 的顺序还原，这样的好处是如果我们每次能保证单次复杂度，那么进入子问题后复杂度同样能得到保证。我们发现每次操作是对区间按奇偶分类，然后再前后分别放入，此外我们能观察到我们不妨令操作区间都为偶数长度区间。我们现在只需要关心待还原的位置，我们希望它往前走，自然能够想到把它放在末尾，将左端点设为目标位置，也就是开头，这样我们的距离就会减少一半，于是此时复杂度 \(\mathcal{O}(n\log n)\)。
提前用操作随机扰动是没用的，因为 \(\log\) 里做减法实在是太逊了。
实在没办法考虑倒着做，尽量不要硬想，这种题基本上不会复杂到哪去。我们倒着做一次操作时区间前一半和后一半取出来然后镶嵌插入。此时发现我们还是可以从前往后还原，不过这样更劣了，我们甚至还得关心 \(2i\) 是否大于 \(n\)，且我们仍然没能优化复杂度，我们还是不能动之前操作过的东西，导致我们的复杂度还是 \(\sum\log (i-j)\) 的状物。
我们发现这个减法在期望下最后求和就是 \(n\log n\)，我们有没有什么厉害的办法可以优化掉一些东西，比如说不能操作之前的东西就很鸡肋。我们发现我们希望操作的是一段前缀，那么我们考虑倒着还原不就不会遇到这种问题了吗？我们倒着还原，对于当前位置 \(i\) 我们希望把它放到 \(n\)，我们操作 \([1,2i]\) 可以让 \(i\) 倍增，如果 \(2i>n\) 直接操作 \([2i-n+1,n]\) 即可一步归位。斯特林公式可以证明，\(\sum \log (\frac i j)\) 是线性的，于是配合上一点随机扰动我们就做完了。
太困难！