#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
int find_best(int n) {
vector<vector<int>> query(n);
function<vector<int>(int)> f = [&](int x)
{
if(query[x].empty())
query[x] = ask(x);
return query[x];
};
function<bool(int, int)> rng = [&](int l, int r)
{
f(l), f(r);
if(query[l][0] + query[l][1] == query[r][0] + query[r][1] and 0 == query[r][0] - query[l][0])
return false;
return true;
};
function<int(int, int)> dandc = [&](int l, int r)
{
int mid = (l + r) / 2;
f(mid);
if(query[mid][0] + query[mid][1] == 0)
return mid;
int ans = -1;
if(rng(l, mid))
ans = max(ans, dandc(l, mid));
if(rng(mid+1, r))
ans = max(ans, dandc(mid+1, r));
return ans;
};
if(f(0)[0] + f(0)[1] == 0)
return 0;
if(f(n-1)[0] + f(n-1)[1] == 0)
return n-1;
return dandc(0, n-1);
}
