#include "prize.h"
#include <bits/stdc++.h>
const int MAXN = 2e5;
std::vector<int> res[MAXN + 10];
std::pair<int,int> get(int i) {
if(!res[i].size()) res[i] = ask(i);
return {res[i][0], res[i][1]};
}
int sum(int i) {
return get(i).first + get(i).second;
}
int cc = 0, ls = 0;
int lowest(int n) {
int mx = 0;
for(int i = 0; i < n && i*i <= n; i++) {
mx = std::max(mx, sum(i));
}
return mx;
}
int solve(int lo, int hi) {
if(lo == hi) {
if(sum(lo) == ls) return -1;
cc++;
if(sum(lo) == 0) return lo;
else return -1;
}
int m = (lo + hi) / 2;
if(sum(m) < ls || get(m).first - cc > 0) {
int rr = solve(lo, m);
if(rr != -1) return rr;
}
if(sum(hi) < ls || get(hi).first - cc > 0) {
int rr = solve(m+1, hi);
if(rr != -1) return rr;
}
return -1;
}
int find_best(int n) {
ls = lowest(n);
return solve(0, n-1);
}
