先考虑一个平方的做法。我们先问出 \(1,n\)：遍历所有元素，删掉它以后问一下剩余 \(n-1\) 个元素形成的集合，如果是 \(n-1\) 的倍数说明这个元素要么 \(1\) 要么 \(n\)，由于两个排列是镜像的所以任意钦定一个是 \(1\) 一个是 \(n\) 即可。删掉两个元素以后归纳问剩余部分也可以知道 \(2,n-1\) 的位置，注意这里 \(2\) 和 \(n-1\) 的位置不能随意钦定，任意取二者之一与 \(1\) 一起问即可确定这个位置上元素的奇偶性，由于 \(n\) 是偶数，也可判断其是 \(2\) 还是 \(n-1\)，然后再问 \(3,n-2,\cdots,k,n-k+1\)，这样 \(n\) 轮就可以确定所有元素的位置。
考虑优化。这个做法的缺点在于，我们问了很多大小非常大的集合，感性理解一下如果集合大小很大，那么问出 \(1\) 的概率就会很小，而我们恰恰是用 \(1\) 的询问来确定排列的某些信息的。这就启发我们问一些大小很小的集合。怎么办呢？CRT。考虑 \(S=\{3,5,7,8\}\)，如果我们知道每个位置上的元素模 \(S\) 中每个数的值，就可以 CRT 带回去算出对应的 \(p_i\)。这样思路就出来了，我们先跑 \(B\) 轮上面 \(O(n)\) 的算法得到 \([1,B]\cup[n-B+1,n]\) 中每个数的位置，并且要求任意 \(x\in S\)，\([1,B]\cup[n-B+1,n]\) 存在一个 \(x-1\) 个大小为 \(x-1\) 的子集，满足这些子集中元素之和 \(\bmod x\) 两两不同，这样对于每个 \(x\)，我们询问选出的这 \(x-1\) 个子集与 \(i\) 的并，即可知道 \(p_i\bmod x\)。取 \(B=5\) 即可。因为对于 \(\{1,2,3,4,n-4,n-3,n-2\}\)，\(\{1,2,3,4,n-4,n-3,n-1\}\)，\(\{1,2,3,4,n-4,n-3,n\}\)，\(\{1,2,3,4,n-4,n-2,n\}\)，\(\{1,2,3,4,n-4,n-1,n\}\)，\(\{1,2,3,4,n-3,n-1,n\}\)，\(\{1,2,3,4,n-2,n-1,n\}\)，\(\{1,2,3,5,n-2,n-1,n\}\) 这八个集合而言，相邻两个集合中所有元素之和恰好差 \(1\)，所以它们 \(\bmod 8\) 的值互不相同，因此 \(B=5\) 是 ok 的，而 \(B=4\) 时 \(n\bmod 8=4\) 时显然不合法，因此取 \(5\) 就好了。
好像卡的有点紧。代码同样咕着，等把题解补完了再写代码。