Ones

Radko again wants to know Marti’s sequence $p_1 , p_2 , \dots , p_n$. This time, Marti decided to be more helpful and directly say that the sequence consists of $n$ bits of $0$ and $1$, exactly $k$ of which are $1$. This time he will only answer the following question:

• “Is there a $1$ among $p_l , p_{l+1}, \dots , p_r$?”

Unfortunately, Radko is still too busy and again outsources the task to you. Your program will be tested on $n_{tests}$ subtests for each test, and your score will be calculated based on the total number of questions you use to find the respective sequences.

• Every sequence is uniform random generated.
• $n = 100\,000$
• $n_{tests} = 100$