\(l, r\) を \(1 \leq l \lt r \leq N\) を満たす整数とするとき、 もし \(S_l = 0, S_r = 1\) ならば、\(S_p = 0, S_{p+1} = 1\) を満たす整数 \(p \in [l, r) \coloneqq \lbrace l, l+1, l+2, \ldots, r-2, r-1 \rbrace\) が少なくとも \(1\) 個は存在します。

特に、本問題の制約から \(S_1 = 0, S_N = 1\) なので、\([1, N)\) の範囲に \(S_p = 0, S_{p+1} = 1\) を満たす \(p\) が存在します。 そのうち \(1\) つを見つけ出して出力すれば本問題に正解できます。

\(S_l = 0, S_r = 1\) とし、探索範囲 \([l, r)\) の中から \(S_p = 0, S_{p+1} = 1\) を満たす整数 \(p\) を探し出すことを考えます。 探索範囲の中央の位置 \(m \coloneqq \lfloor \frac{l+r}{2} \rfloor\) について \(S_m\) をジャッジに質問し、その結果が

• \(S_m = 0\) ならば、\(l' \coloneqq m, r' \coloneqq r\)、
• \(S_m = 1\) ならば、\(l' \coloneqq l, r' \coloneqq m\)

とおくと、\(S_{l'} = 0, S_{r'} = 1\) を満たし、\(p\) の探索範囲を区間 \([l', r')\) に絞ることができます。 \(l', r'\) を新たに \(l, r\) と置き直してこの手順を繰り返すことで探索範囲を狭めていき、最終的に \(l+1 = r\) となれば、 \(p \coloneqq l\) として所望の \(p\) が得られます。

\(1\) 回の質問で探索範囲の長さを \(r' - l' \leq \max\lbrace m-l, r-m \rbrace \leq \lceil \frac{r-l}{2} \rceil\) とほぼ半分に減らすことができるため、\(l = 1, r = N\) の初期状態から高々 \(\lceil \log_2 N \rceil \leq 18\) 回の質問で所望の \(p\) を見つけることができます。