Leak in the Pipeline

A long pipeline is split into sections 1..n, and exactly one of them leaks. A pressure sensor can be placed after any section k: it reports True if the leak is in sections 1..k and False if it is further along. Readings are expensive: you may take at most ⌈log2 n⌉ of them.

Write find_leak(n, sensor) that returns the number of the leaking section. Call sensor(k) to take a reading; one reading too many raises TooManyQuestions.

The tests run with_sensor(find_leak, n, seed), which hides the leak and counts your readings. Try it with Run: print(with_sensor(find_leak, 100, 1)).

Examples

Input:  with_sensor(find_leak, 8, 1)   (the leak is hidden in one of 8 sections; 3 readings)
Output: {"answer": ..., "readings": ..., "limit": 3, "leak": ...}
        correct when answer == leak

Constraints

• 1 <= n <= 10**9
• at most ⌈log2 n⌉ readings (0 readings when n == 1)

Goals

• Find a hidden value by asking yes/no questions
• Stay within a question budget of about log2(n)