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$