#include "prize.h"
#include <vector>
#include <map>
using namespace std;
map<int, vector<int>> dp;
int search(int l, int r) {
if (l > r) return -1;
if (l == r) {
vector<int> ans;
if (dp.find(l) != dp.end()) ans = dp[l];
else {
ans = ask(l);
dp[l] = ans;
}
if (ans[0] == 0 && ans[1] == 0) return l;
return -1;
}
int m = (l+r)/2;
vector<int> ans;
if (dp.find(m) != dp.end()) ans = dp[m];
else {
ans = ask(m);
dp[m] = ans;
}
if (ans[0] == 0 && ans[1] == 0) return m;
else if (ans[0] == 0) {
return search(m+1, r);
}
else if (ans[1] == 0) {
return search(l, m-1);
}
else {
int ans1, ans2;
ans1 = search(l, m-1);
ans2 = search(m+1, r);
return (ans1 == -1 ? ans2 : ans1);
}
return -1;
}
int find_best(int n) {
return search(0, n-1);
}
