#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;
vector<vector<ll>> degBoxes(n);
set<ll> degs;
for (int i = n-1; i >= n - 2*root && i >= 0; i--) {
ll deg = get(i).first + get(i).second;
degBoxes[deg].push_back(i);
mxDeg = max(mxDeg, deg);
degs.insert(deg);
}
int m = max(n - 2*root, 0);
if (!degBoxes[0].empty()) {
return degBoxes[0][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) {
degBoxes[deg].push_back(mid);
mid--;
val = get(mid);
deg = val.first + val.second;
cnt++;
}
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;
degBoxes[get(left).first + get(left).second].push_back(left);
vst[i] = true;
}
return degBoxes[0][0];
}
