#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
map<int,pii> res;
pii get(int x){
if(res.count(x)) return res[x];
vector<int> g = ask(x);
res[x] = mp(g[0], g[1]);
return mp(g[0],g[1]);
}
int low = 0;
int n;
int solve(int li, int ri, int know){
if(li > ri || know == 0) return -1;
pii ash = get(li);
if(ash.fi + ash.se == 0) return li;
if(li == ri) return -1;
int mid = (li + ri) / 2;
int qq = mid;
pii cc;
while(qq >= li){
cc = get(qq);
if(cc.fi + cc.se == 0) return qq;
if(cc.fi + cc.se < low){
qq -- ;
}
else{
break;
}
}
int qa = solve(li, qq - 1, ash.se - cc.se);
if(qa != -1) return qa;
int qb = solve(qq, ri, know - (ash.se - cc.se));
return qb;
}
int find_best(int _n) {
n = _n;
pii cur;
for(int i = 0 ; i < min(n,500); i ++ ){
cur = get(i);
if(cur.fi + cur.se == 0)
return i;
low = max(low, cur.fi + cur.se);
}
int lef = 0, rig = n - 1;
while(1){
pii cc = get(lef);
if(cc.fi + cc.se == 0) return lef;
if(cc.fi + cc.se != low)
lef ++ ;
else
break;
}
while(1){
pii cc = get(rig);
if(cc.fi + cc.se == 0) return rig;
if(cc.fi + cc.se != low)
rig -- ;
else
break;
}
pii sa = get(lef);
pii sb = get(rig);
return solve(lef, rig, sa.se-sb.se);
}
