Find the Zero

The query is secretly a zero-detector

All nonzero values $1,2,\dots,n$ are unique. Therefore for $i\ne j$,

$$a_i=a_j \Longleftrightarrow a_i=a_j=0.$$

So if a query returns $1$, both positions are zeros and we can immediately output either endpoint. A return value $0$ is weaker: it only says the pair does not contain two zeros.

The adaptive judge detail matters. We are not trying to identify its current array. We are trying to make the transcript force some position to be zero in every valid array. The judge can be slippery, but arithmetic still punches it in the face.

Reserve two positions

Do not query $(1,2)$. Query the $n-1$ disjoint pairs

$$(3,4),(5,6),\ldots,(2n-1,2n).$$

If any pair returns $1$, output its first endpoint.

Now consider the only annoying case: all these answers are $0$. Let $P_i=(2i+1,2i+2)$, and let $z(S)$ be the number of zeros inside positions $S$. For every queried pair,

$$z(P_i)\le 1.$$

So among positions $3,4,\ldots,2n$ there are at most $n-1$ zeros:

$$\sum_{i=1}^{n-1} z(P_i)\le n-1.$$

But the whole array contains exactly $n$ zeros, hence

$$z(\{1,2\})\ge 1.$$

Great: at least one of positions $1$ and $2$ is zero.

Use pair $(3,4)$ as a witness

We still need to know which of $1$ or $2$ is guaranteed. We have two queries left, because

$$(n-1)+2=n+1.$$

Query $(1,3)$ and, if needed, $(1,4)$.

If either query returns $1$, then position $1$ equals a zero, so $a_1=0$ and we output $1$.

If both return $0$, output $2$. Here is the count argument, because this is where the magic happens and also where wrong solutions eat dirt.

Assume for contradiction that $a_2\ne0$. Since at least one of $1,2$ is zero, we must have $a_1=0$. Because both $(1,3)$ and $(1,4)$ returned $0$, neither $3$ nor $4$ can be zero. Thus pair $(3,4)$ contains no zeros. The remaining $n-2$ queried pairs contain at most one zero each, so the total number of zeros is at most

$$1+0+(n-2)=n-1,$$

contradicting that there are exactly $n$ zeros. Therefore $a_2=0$.

Complexity

The algorithm uses at most

$$(n-1)+2=n+1$$

queries per test case, exactly within the limit. The running time is $O(n)$ per test case and the memory usage is $O(1)$.

Sources checked: Codeforces statement, official contest editorial.