Guess the Number with a Comparator

A secret integer lies in 1..n. You are given n and a function compare(g) that returns

• 0 if g is the secret,
• -1 if g is larger than the secret,
• 1 if g is smaller than the secret.

Return the secret. The tests build compare from a hidden value, e.g. lambda g: (secret > g) - (secret < g).

Examples

Input:  n = 10, compare = lambda g: (6 > g) - (6 < g)
Output: 6

Input:  n = 1, compare = lambda g: 0
Output: 1

Constraints

• 1 <= n <= 10**9
• Your function may call compare at most 40 times; trying values one by one will time out.

Goals

• Drive a binary search with feedback from a function instead of list values
• Interpret a three-way comparison result correctly