#include<bits/stdc++.h>
#include "prize.h"
using namespace std;
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;
vector<vector<int>> resp;
int querycount = 0;
vector<int> query(int id){
if(resp[id][0] == -1){
querycount++;
resp[id] = ask(id);
}
return resp[id];
}
int find_best(int n) {
resp = vector<vector<int>>(n,{-1,-1});
int ct = 0;
vector<int> cand;
bool flag = 0;
auto solve =[&](int l, int r, int discl, int discr, auto solve)->void{
if(r < l)
return;
if(discl + discr == ct)
return;
int m = (l+r)>>1;
int mid = m;
vector<int> ret = query(m);
while(m <= r && ret[0]+ret[1] < ct){
cand.push_back(m);
m++;
if(m <= r)
ret = query(m);
}
if(ret[0]+ret[1] > ct){
flag = 1;
return;
}
if(m > r){
int m = mid-1;
if(m < l)
return;
ret = query(m);
while(m >= l && ret[0]+ret[1] < ct){
cand.push_back(m);
m--;
if(m >= l)
ret = query(m);
}
solve(l,m-1,discl,ret[1],solve);
return;
}
solve(l,mid-1,discl,ret[1]+m-mid,solve);
solve(m+1,r,ret[0],discr,solve);
};
do{
cand.clear();
flag = 0;
solve(0,n-1,0,0,solve);
} while(flag);
for(int i : cand){
vector<int> ret = query(i);
if(ret[0]+ret[1] == 0){
return i;
}
}
}
