この問題は、毎回の質問で \(x\) の候補の数を半分以下にしていく方針で解くことができます。

点 \(i\) が点 \(j\) から \(A_{i,j}\) 番目に近いとします。 ある \(r\) によって \(\{1\le j\le N\ |\ A_{i,j}=r\}\) と書ける集合を \(A_i\) の等高線と呼ぶことにします。

このとき以下が成り立ちます。

以下の条件 (P) をみたす \(i\) が存在する。
条件 (P) : \(A_i\) の任意の等高線のサイズは \(N/2\) 以下である。

条件 (P) をみたす \(i\) を探して質問をすることを考えます。この質問によって \(x\) の候補は高々2つの区間になります。 \(x\) の候補が1つの区間のときは \(N\) が半分以下になっている場合に帰着します。 また、2つの区間に分かれているときは、長い方の区間に \(x\) が存在すると仮定して同様の質問を行うことにすればよいです。 すると、毎回の質問で \(x\) の候補は半分以下になるため、高々 \(\lfloor \log_2{N}\rfloor\) 回の質問を行った時点で1通りに定まります。

条件 (P) をみたす \(i\) の探し方

\(A\) をすべて計算するのは制約上不可能なので、効率的に \(i\) を探さなければいけません。

実は、以下のようにして \(i\) を得ることができます。

区間 \(I\) を \([1,N](=\{1,\dots,N\})\) で初期化して、以下の手順を繰り返す。

• いま \(I=[l,r]\) であるとして、\(P_m=\max\{P_j\ |\ l\le j<r\}\) となる \(m\) をとる。もし \([l,m]\) と \([m+1,r]\) の大きさがともに \(N/2\) 以下であれば手順を終了する。そうでなければ \(I\) を \([l,m]\) と \([m+1,r]\) のうち小さくない方の区間に更新する。

最終的に得られた \(I\) の端点のうち、条件 (P) をみたすものが存在する。

証明

最終的に \(I=[l,r]\) になったとする。このとき任意の \(i\in[l,r]\) について、\(A_i\) の等高線の各区間の大きさは高々 \(N/2\) である。（すなわち 2 区間に分かれているような等高線のみが問題になる。）

ここで、（一般の \(i\in[1,N]\) について）2 区間に分かれているような \(A_i\) の等高線 \([a,b]\cup[c,d]\) は \(i-a=d-i\) をみたすことに注意する。

さて、 \([l,r]\) のつくり方から \( \# [l,r]>N/2\) である。したがって \(l\le\lceil N/4\rceil\) または \(r\ge N+1-\lceil N/4\rceil\) が成り立つ。

前者がみたされているときには、\(A_l\) の2区間に分かれている等高線 \([a,b]\cup[c,d]\) は \(l-a=d-l\) をみたすので、 \(\#[a,b]\cup[c,d]\le d-1=2l-a-1\le N/2\) と評価できる。すなわち \(l\) は条件 (P) をみたす。

後者がみたされているときも同様に、\(r\) は条件 (P) をみたすことが分かる。

上をセグメント木を用いて実装すれば、\(O(N\log N)\) で条件 (P) をみたす \(i\) を探し出すことができます。したがって全体で \(O(N\log N+(N/2)\log N+\cdots)=O(N\log N)\) で解けました。

乱択による解法

\(i\) が条件 (P) を満たすまで乱択し続けることでも本問を解くことができます。

条件 (P) をみたす \(i\) の個数について考えます。

サイズが \(\lfloor N/2\rfloor+1\) 以上の等高線の高さ \(r\) は、 \(\lfloor N/2\rfloor+2\) 以上でなければならないので高々 \(\lfloor N/2\rfloor\) 種類しか存在しません。また、 \(A\) には \(1,\dots,N\) がそれぞれちょうど \(N\) 回ずつ現れるので、サイズ \(\lfloor N/2\rfloor+1\) 以上の等高線の高さは相異なります。したがって条件 (P) をみたす \(i\) は \(\lceil N/2\rceil\) 個以上存在し、乱択アルゴリズムによって十分高速に得ることができます。