#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
typedef long long ll;
vector<pair<int, int>> cache;
pair<int, int> get(int i) {
if (cache[i].first >= 0) return cache[i];
auto res = ask(i);
return cache[i] = {res[0], res[1]};
}
int find_best(int n) {
cache = vector<pair<int, int>>(n, {-1, -1});
int root = (int)ceil(sqrt(n));
ll mxDeg = 0;
for (int i = n-1; i >= n - 2*root && i >= 0; i--) {
ll deg = get(i).first + get(i).second;
if (deg == 0) return i;
mxDeg = max(mxDeg, deg);
}
int m = max(n - 2*root, 0);
int prevLeft = 0;
vector<bool> vst(mxDeg);
for (int i = 0; i < mxDeg; i++) {
if (vst[i]) continue;
int left = prevLeft, right = m-1;
while (left < right) {
int mid = (left+right+1)/2;
pair<int, int> val = get(mid);
int deg = val.first + val.second;
int cnt = 0;
while (deg < mxDeg && mid > 0) {
if (deg == 0) return mid;
mid--; right--;
val = get(mid);
deg = val.first + val.second;
cnt++;
}
if (deg == 0) return mid;
if (cnt > 0) {
int ptr = 0;
while (cnt--) vst[val.first + ptr++] = true;
}
if (vst[i]) break;
if (val.first <= i) {
left = mid;
}
else {
right = mid-1;
}
}
if (vst[i]) continue;
if(get(left).first + get(left).second == 0) return left;
vst[i] = true;
}
return 0;
}
