まず、\(P_x = 1\) となる整数 \(x\) を特定します。これは、以下のようにすることで \(N-1\) 回の質問で特定可能です。

• $x=1$ とする。$i=2,3,\dots,N$ の順に以下を行う。
• $P_i + P_i > P_x$ かどうかを聞く。返答が No ならば $x=i$ とする。

最終的な \(x\) が \(P_x=1\) を満たします。

重要な性質として、\(a,b\) が相異なる整数であるとき、\(a+1 > b\) と \(a>b\) は同値です。よって、\(P_a + P_x > P_b\) かを聞くことによって、任意の \(2\) 要素の大小が分かります。

なので、\(P_1,P_2,\dots,P_{x-1},P_{x+1},\dots,P_N\) に対してマージソートを行うことで高々 \(N\lceil \log_2(N) \rceil\) 回の質問で \(P_1,P_2,\dots,P_{x-1},P_{x+1},\dots,P_N\) をソートすることが出来ます。よって、全ての整数 \(i\) に対して \(P_i\) を求めることが出来ます。

\(N=2000\) のとき、\(N-1 + N\lceil \log_2(N) \rceil=23999\) より質問回数の制約も満たします。