使えるクエリの回数が少ない事を考えると、全ての数列の要素を特定する事は出来ません。端の要素だけ特定する必要があります。

\(N\) 頂点の無向グラフであって、\(|a_i-a_j|\leq K (i\neq j)\) を満たす \(i,j\) について辺を張ったものを考えます。この時、ほとんどの頂点の次数は \(2K\) ですが、端の方の頂点の次数は \(2K\) より小さくなります。頂点の端度を \(2K-{}\)(その頂点の次数) と定めると、全頂点の端度の和は \(K(K+1)\) で、\(x,y\) で端度は最大値の \(K\) を取ります。

ここで、クエリの返り値は誘導部分グラフの辺の数と解釈することが出来ます。ここである頂点集合 \(S\) について、\(S\) の誘導部分グラフの辺の数と \(S\) の補集合の誘導部分グラフの辺の数の差は、\(S\) に含まれる頂点の次数の和と\(S\) の補集合に含まれる頂点の次数の和の差の \(2\) 倍になります。よって、クエリを \(2\) 回使う事である頂点集合 \(S\) の次数の和が分かり、頂点集合 \(S\) の端度の和も分かります。

\(x,y\) を含む可能性を含む頂点集合の集合族 \(\{A_i\}_{i=1}^m\) を更新することでこの問題は解くことが出来ます。最初 \(\{A_i\}_{i=1}^m\) の要素は全ての頂点の集合のみです。\(\{A_i\}_{i=1}^m\) に含まれる集合全てについて集合を二つに分け、端度の和が \(K\) 未満であるものを \(\{A_i\}_{i=1}^m\) から除外するという操作を行います。全頂点の端度の和が \(K(K+1)\) 以上である事から、\(\{A_i\}_{i=1}^m\) の要素数は常に \(K+1\) 個以下であることが分かります。よって、\((K+1)\times 15 \times 2=30(K+1)\) 回以下のクエリで \(x,y\) を求めることが出来ます。