Let \(l\) and \(r\) be integers such that \(1 \leq l \lt r \leq N\). If \(S_l = 0\) and \(S_r = 1\), then there is at least on e integer \(p \in [l, r) \coloneqq \lbrace l, l+1, l+2, \ldots, r-2, r-1 \rbrace\) such that \(S_p = 0\) and \(S_{p+1} = 1\).

Especially, the Constraints \(S_1 = 0\) and \(S_N = 1\) of this problem always guarantee that a \(p\) exists within the range \([1, N)\). We need to find one such \(p\) and print it to be accepted. We solve this problem with binary search.

Consider finding an integer \(p\) such that \(S_p = 0\) and \(S_{p+1} = 1\) within a range \([l, r)\) such that \(S_l = 0\) and \(S_r = 1\). Ask the judge about \(S_m\) for the midpoint \(m \coloneqq \lfloor \frac{l+r}{2} \rfloor\) of the searching range.

• if \(S_m = 0\), then let \(l' \coloneqq m\) and \(r' \coloneqq r\);
• if \(S_m = 1\), then let \(l' \coloneqq l\) and \(r' \coloneqq m\);

then, \(S_{l'} = 0\) and \(S_{r'} = 1\) are still satisfied, while the range of \(p\) is narrowed down to \([l', r')\). Successively replace \(l\) and \(r\) with these \(l'\) and \(r'\), respectively, to narrow down the searching range. Once we reach \(l+1 = r\), we can find the desired \(p\) as \(p \coloneqq l\).

Since each query almost halves the length of searching range as \(r' - l' \leq \max\lbrace m-l, r-m \rbrace \leq \lceil \frac{r-l}{2} \rceil\), the desired \(p\) can be found with at most \(\lceil \log_2 N \rceil \leq 18\) queries, starting from \(l = 1, r = N\).