#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 ls = 0;
int lowest(int n) {
int mx = 0;
for(int i = 0; i*i < n; i++) {
mx = std::max(mx, sum(i));
}
return mx;
}
int solve(int lo, int hi, int lc, int cc) {
if(!cc || lo > hi) return -1;
if(lo == hi) {
if(sum(lo) == 0) return lo;
else return -1;
}
int m = (lo + hi) / 2;
int ml = m, lf = 0;
while(ml >= lo && sum(ml) < ls) {
lf++;
ml--;
}
if(ml >= lo) lf += get(ml).first - lc;
int rr = solve(lo, m, lc, lf);
if(rr != -1) return rr;
rr = solve(m+1, hi, lc+lf, cc-lf);
if(rr != -1) return rr;
return -1;
}
int find_best(int n) {
ls = lowest(n);
return solve(0, n-1, 0, ls);
}
