#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 ga = get(li);
if(ga.fi + ga.se == 0) return li;
pii gb = get(ri);
if(gb.fi + gb.se == 0) return ri;
if(li == ri) return -1;
int na = li;
int nb = ri;
if(ga.fi + ga.se < low) {
na ++ ;
if(know != -1)
know -- ;
}
if(gb.fi + gb.se < low) {
nb -- ;
if(know != -1)
know -- ;
}
if(na != li || nb != ri){
return solve(na, nb, know);
}
know = ga.se - gb.se;
int lef = know;
int mid = (li + ri) / 2;
int la = mid;
while(la > li){
pii cc = get(la);
if(cc.fi + cc.se == 0) return la;
if(cc.fi + cc.se < low) la --, lef -- ;
else break;
}
int aq = solve(li, la, lef);
if(aq != -1) return aq;
return solve(mid + 1, ri, know - lef);
}
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);
}
return solve(0, n - 1, -1);
}
