#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 next(int lo, int hi) {
while(lo < hi) {
int m = (lo + hi) / 2;
if(sum(m) < ls) hi = m;
else if(get(m).first-cc > 0) hi = m-1;
else lo = m+1;
}
return lo;
}
int find_best(int n) {
ls = lowest(n);
int l = 0;
while(l < n) {
l = next(l, n-1); cc++;
if(sum(l) == 0) return l;
l++;
}
return -1;
}
