First, let us identify the integer \(x\) such that \(P_x = 1\). It can be done in \(N-1\) questions as follows.

• Let $x=1$. For $i=2,3,\dots,N$ in this order, do the following.
• Ask whether $P_i + P_i > P_x$. If the answer is No, let $x=i$.

The final \(x\) satisfies \(P_x=1\).

Here is an important property: if \(a\) and \(b\) are different integers, \(a+1 > b\) if and only if \(a>b\). Thus, asking whether \(P_a + P_x > P_b\) reveals the larger between any two elements.

Therefore, by performing merge sort on \(P_1,P_2,\dots,P_{x-1},P_{x+1},\dots,P_N\), you can sort \(P_1,P_2,\dots,P_{x-1},P_{x+1},\dots,P_N\) in at most \(N\lceil \log_2(N) \rceil\) questions, finding \(P_i\) for all \(i\).

For \(N=2000\), you will ask at most \(N-1 + N\lceil \log_2(N) \rceil=23999\) questions, which is within the limit.