#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 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);
}
int p = -1;
int cc;
int li, ri, mid;
pii nw;
while(1){
cc = p + 1;
cur = get(cc);
if(cur.fi + cur.se == 0)
return cc;
if(cur.fi + cur.se < low){
p = cc;
}
else{
li = cc, ri = n-1;
while(li < ri){
mid = (li + ri) / 2;
nw = get(mid);
if(nw.fi + nw.se == 0)
return mid;
if(nw.fi + nw.se < low){
ri = mid;
}
else{
if(nw.fi - cur.fi == 0)
li = mid + 1;
else
ri = mid;
}
}
cur = get(li);
if(cur.fi + cur.se == 0)
return li;
p = li;
}
}
return -1;
}
