1 찾기

Radko는 이번에도 Marti가 정한 수열 $p_1, p_2, \dots, p_n$을 알아내고 싶어 한다. 이번에 Marti는 더 도움을 주기로 하고, 수열이 $n$개의 비트 0과 1로 이루어져 있으며 그중 정확히 $k$개가 1이라고 직접 밝혔다. 그는 이번에도 다음 질문에만 답한다.

• $p_l, p_{l+1}, \dots, p_r$ 중에 1이 있는가?

안타깝게도 Radko는 여전히 너무 바빠서 이 작업을 다시 당신에게 맡긴다. 프로그램은 테스트마다 $n_{tests}$개의 부분 테스트에서 실행되며, 점수는 각 수열을 찾는 데 사용한 질문의 총 개수로 정해진다.

• 모든 수열은 균일한 무작위 방식으로 생성된다.
• $n = 100000$
• $n_{tests} = 100$