直接被这个题闪到了。
首先发现 \(1\) 是最小的，其有很多性质，因此可以花费 \(n - 1\) 次操作比较出来 \(1\) 的位置。
同理，\(2, 3, ..., n\) 都是可以这样比较出来的，但操作次数是 \(O(n^2)\) 级别的，题目只给了我们 \(O(n \log n)\) 次操作。
注意到 \(p_i + 1 > p_j \to p_i \ge p_j\)，也就是我们可以通过一次操作比较两个数的关系，这显然可以用归并排序等理论信息论比较在 \(O(n \log n)\) 级别的排序算法解决该问题。