#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;
int sol = -1;
pii get(int x){
if(res.count(x)) return res[x];
vector<int> g = ask(x);
if(g[0] + g[1] == 0) sol = x;
return res[x]=mp(g[0],g[1]);
}
int find_best(int n) {
int li=-1;
int nl, nr;
int cnt;
int value;
vector<int> has;
while(1){
nl=li+1,nr=n;
int mid;
while(nl + 1 < nr){
mid = (nl + nr) / 2;
pii cur = get(mid);
value = cur.fi + cur.se;
cnt = 0;
for(auto x : has){
if(x < value){
cnt ++ ;
}
}
if(cur.fi > cnt){
nr = mid-1;
}
else{
nl = mid;
}
}
pii cur = get(nl);
value = cur.fi + cur.se;
has.push_back(value);
li=nl;
if(sol != -1) return sol;
}
return -1;
}
