#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 == -1) 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 ca = mid;
int cb = mid + 1;
while(ca >= li){
ash = get(ca);
if(ash.fi + ash.se == 0) return ca;
if(ash.fi + ash.se < low){
ca -- ;
know -- ;
}
else{
break;
}
}
pii fa = get(li);
ash = get(ca);
int faf = fa.se - ash.se;
int tri = solve(li, ca, faf);
if(tri != -1) return tri;
while(cb <= ri){
ash = get(cb);
if(ash.fi + ash.se == 0) return cb;
if(ash.fi + ash.se < low){
cb ++ ;
know--;
}
else{
break;
}
}
return solve(cb, ri, know - faf);
}
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);
}
