$m = n \lceil \log n \rceil$

算法的核心思路是从 $0$ 到 $n$ 依次通过二分确定位置。

首先可通过二分询问 $(0,x)$ 确定 $0$ 的位置。对于 $i>0$，利用一次询问即可判断其位于 $0$ 的左侧还是右侧。若在右侧，则令 $L$ 为 $0\sim i-1$ 所在位置的最小值，并二分询问 $(L,x)$ 以找到第一个包含 $i$ 的位置，随后再检查该位置的值是否确为 $i$。

若 $i$ 右侧存在更小的数（即 $i$ 的左右两侧均有严格小于自身的数），则 $i$ 的精确位置实际上是无法被唯一确定的。此时任意合法的构造中，只需保证 $i$ 既不充当前缀最小值也不充当后缀最小值即可。在上述二分过程中，直接将 $i$ 放置于当前区间的任意空位便可满足条件。

对于特殊性质 C，由于前缀最小值的期望个数仅有 $O(\log n)$ 个，通过优化实现逻辑可在 $O(\log^2 n)$ 次询问内完成序列的还原。

$m = n$

对于特殊性质 A，记 $Q(l,r)$ 为询问区间 $[l,r]$ 的答案。通过依次对所有 $(0,x)$ 进行询问，若观测到 $Q(0,x) \neq Q(0,x+1)$，便可直接推断出 $p_{x+1}=Q(0,x)$。

以此方式能够稳妥地找出所有的后缀最小值，整体过程在 $n$ 次询问内即可完成。

对于特殊性质 B，可以先定位 $0$ 的位置，随后向序列的两侧进行扩展。

对于一般情况，可采用类似的思路：首先精确定位 $0$ 的位置，然后对于 $0$ 右侧的位置 $x$，比较 $Q(0,x)$ 与 $Q(0,x+1)$ 的差异；对于 $0$ 左侧的位置 $x$，则比较 $Q(x,n-1)$ 与 $Q(x-1,n-1)$ 的差异。与考察特殊性质 A 时的方法类似，该策略同样能找出所有的前缀最小值与后缀最小值。

在具体算法实现中，可连续询问 $Q(i,n-1)$ 直至 $Q(i,n-1)$ 的返回值变为 $0$。该时刻即可精确确定 $0$ 的位置，随后转向询问序列的另一侧，由此保证总询问次数被严格限制在 $n$ 次。