Locate

Big Picture

The query gives only

$$\max(p_l,\ldots,p_r)-\min(p_l,\ldots,p_r).$$

That is annoyingly symmetric. If we replace every value by $n+1-p_i$, every query answer stays identical, because max and min just swap around. But the position of $n$ becomes the position of $1$. So without Player A's bit, Player B can be forced to confuse $n$ and $1$. That is not a bug in your brain, that's the problem being a little bastard.

So Player A should use the single bit to break this exact symmetry.

We will send:

$$x = [\operatorname{pos}(n) < \operatorname{pos}(1)].$$

Now Player B only needs to recover the two possible positions that could be $1$ and $n$, up to complement symmetry. Then this bit chooses the right one.

The Key Search

Define

$$f(l,r)=\max(p_l,\ldots,p_r)-\min(p_l,\ldots,p_r).$$

Player B binary searches for the smallest index $k$ such that

$$f(1,k) \ge n-2.$$

Why is this useful?

A range of at least $n-2$ means the interval contains two values whose difference is $n-2$ or $n-1$. In a permutation of $1\ldots n$, the only unordered pairs with difference at least $n-2$ are:

$$\{1,n\},\quad \{1,n-1\},\quad \{2,n\}.$$

Since $k$ is the first prefix where this happens, $[1,k-1]$ does not contain such a pair. Therefore the newly added value $p_k$ must participate in the first extreme pair.

Let

$$a=f(1,k), \qquad b=f(2,k).$$

There are two cases.

Case 1: $b < n-2$

Removing position $1$ destroys the large range. That means position $1$ and position $k$ are the two endpoints of the first extreme pair.

So the ambiguous candidate positions are simply:

$$1 \quad \text{and} \quad k.$$

Among these, one is the position of $n$ in the original permutation, and the other is the position of $1$ in the complemented permutation. The bit $x$ tells us which one is earlier in the true permutation:

• if $x=1$, then $\operatorname{pos}(n)<\operatorname{pos}(1)$, so choose the earlier candidate;
• if $x=0$, choose the later candidate.

Since the candidates are $1$ and $k$, this is immediate.

Case 2: $b \ge n-2$

Then after removing position $1$, the large range still exists inside $[2,k]$. Since $k$ was the first good prefix, the newly added position $k$ is one endpoint, and the other endpoint lies somewhere in $[2,k-1]$.

Now we find that other endpoint.

Binary search for the largest $j<k$ such that

$$f(j,k) \ge n-2.$$

Then $j$ is the position of the other endpoint. The same minimality/maximality logic applies: once we move the left boundary past the endpoint, the large range disappears.

So the ambiguous candidates are:

$$j \quad \text{and} \quad k.$$

Again, the oracle cannot distinguish the original permutation from its complemented version. But Player A's bit does.

• If $x=1$, $n$ is before $1$, so answer the smaller candidate.
• If $x=0$, answer the larger candidate.

Why This Actually Works

The only real subtlety is whether the two candidates always represent the order of $n$ and $1$ correctly enough for the bit.

Suppose the found pair is $\{2,n\}$ in the original permutation. Great: one candidate is directly $n$.

If the found pair is $\{1,n-1\}$ instead, then in the complemented permutation it becomes $\{n,2\}$. Every query answer is identical under this complement, so Player B cannot tell which interpretation is true from queries alone. That is exactly why the bit was needed.

The bit $x=[\operatorname{pos}(n)<\operatorname{pos}(1)]$ flips under complementation, and the two candidate positions swap roles. Therefore choosing the earlier candidate when $x=1$ and the later candidate when $x=0$ is consistent in both indistinguishable worlds.

This is the entire trick: we do not try to fully reconstruct anything. We just find the first interval that is forced to contain an extreme pair, then use one bit to pick the correct side.

Query Count

We use:

• about $\lceil \log_2 n\rceil$ queries to find $k$;
• one query for $f(2,k)$;
• maybe another $\lceil \log_2 n\rceil$ queries to find $j$.

Since $n\le 10^4$, this is at most about $14+1+14=29$ queries. Under the limit of $30$. Tight, but not cursed.

First Run

Player A knows the permutation, so it finds positions of $1$ and $n$ and prints:

$$[\operatorname{pos}(n)<\operatorname{pos}(1)].$$

Second Run

Player B only receives $n$ and $x$, performs the range queries above, and reports the selected position.