\((s_i,l_i)=(i,1)\ (0\leq i < N)\) としたクエリで最小の整数の位置を特定してみましょう。 クエリの回答が \(N\) 個すべての文字列を含む場合、答えは \(i\ (0\leq i <N)\) すべてです。

そうでない場合、 \(A_i\) が最小の整数かつ \(A_{i-1}\) が最小の整数でないような \(i\) の集合 \(T_{cand}=\{x_1,x_2,\dots,x_n\}\) を考えます。

このとき、 \(A(i,N)\) の先頭何項が最小の整数に等しくなるかに着目すると、 \(A(i,N)\) が最小となるような \(i\) はすべて \(T_{cand}\) に含まれていることがわかります。

さらに、 \(A\) を \(n\) 個の整数列 \(B_k=A(x_{k},x_{k+1}-x_k)\ (0 \leq k < n)\) にわけると、 \(A(x_i,N)\) と \(A(x_j,N)\) の比較は、整数列からなる列 \((B_{i},B_{i+1},\dots,B_{i-1})\) と \((B_{j},B_{j+1},\dots,B_{j-1})\) の辞書順での比較と一致します。これは各 \(B_k\) の \(1\) 文字目が最小の整数であることと、末尾が最小の整数ではないことから示せます。

よって以降のクエリでは \(B_i\) が \(1\) つの整数であるように考える（いわゆる座標圧縮をほどこす）ことで、長さ \(|T_{cand}|\) の整数列に対する問題に帰着できます。 \(i \in T_{cand}\) に対し \(i-1 \notin T_{cand}\) であることから \(2|T_{cand}| \leq N\) であり、整数列の長さが半分になっているため、この帰着を高々 \(\lceil\log_2{N}\rceil\) 回繰り返すことで答えを求めることができ、クエリの回数の制約を満たしています。

この帰着の際、クエリでは \(\{(x_i,x_{i+1}-x_i)|i=1,2,\dots,n\}\) をクエリすることになるため、 \(l\) の総和に関する条件は常に満たされています。