#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 solve(int li, int ri){
if(li > ri) return -1;
while(li <= ri){
pii cur = get(li);
if(cur.fi + cur.se == 0) return li;
if(cur.fi + cur.se == low){
break;
}
li ++ ;
}
while(ri >= li){
pii cur = get(ri);
if(cur.fi + cur.se == 0) return ri;
if(cur.fi + cur.se == low){
break;
}
ri -- ;
}
if(li > ri) return -1;
int has = get(ri).fi - get(li).fi;
if(has == 0) return -1;
int cl = li, cr = ri;
int mid;
int sol0, sol1;
while(cl < cr){
mid = (cl + cr) / 2;
pii cur = get(mid);
if(cur.fi + cur.se == 0)
return mid;
if(cur.fi + cur.se == low){
pii lf = get(li);
pii rf = get(ri);
sol0 = sol1 = -1;
if(cur.fi - lf.fi > 0){
sol0 = solve(li + 1, mid - 1);
}
if(rf.fi - cur.fi > 0){
sol1 = solve(mid + 1, ri - 1);
}
if(sol0 == -1) return sol1;
return sol0;
}
else{
cr = mid;
}
}
return -1;
}
int find_best(int 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);
}
