#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
int find_best(int n) {
int sum = 0, pos = -1;
vector<int> ar;
int k = 500;
for(int i = 0 ; i < k ; i++)
{
ar = ask(i);
if(ar[0] + ar[1] == 0)
return i;
sum = max(sum, ar[0] + ar[1]);
}
pos = k - 1;
while(true)
{
pos++;
ar = ask(pos);
if(ar[0] + ar[1] == 0)
return pos;
if(ar[0] + ar[1] == sum)
break;
}
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 query[l][0] + query[l][1] == sum and 0 == query[r][0] - query[l][0])
return false;
return true;
};
function<int(int, int)> dandc = [&](int l, int r)
{
if(l == r)
return (query[l][0] + query[r][1] == 0 ? l : -1);
int mid = (l + r) / 2, 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;
};
return dandc(pos, n-1);
}
