#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> buf;
vector<int> qry(int x) {
if (buf[x].empty()) {
buf[x] = ask(x);
}
return buf[x];
}
int find_best(int n) {
buf.clear(), buf.resize(n);
vector<int> cand;
for (int i = 0; i < n; i++) {
cand.push_back(i);
}
int lvl = 5;
vector<int> s(6);
while (cand.size() > 1) {
int l = 0, r = 500;
while (l + 1 < r) {
int m = l + (r - l) / 2;
int t = m, sum = t * t + 1 + t;
while (t > 1) {
t = sqrt(t);
sum += t;
}
if (sum <= cand.size()) {
l = m;
} else {
r = m;
}
}
int lim = 1, t = l;
while (t > 1) {
lim += t;
t = sqrt(t);
}
for (int i = 0; i < lim; i++) {
vector<int> res = qry(cand[i]);
s[lvl] = max(s[lvl], res[0] + res[1]);
}
vector<int> pidx;
for (int i = 1; i <= s[lvl]; i++) {
int l = -1, r = cand.size() - 1;
while (l + 1 < r) {
int rm = l + (r - l) / 2, lm = rm;
vector<int> res = qry(cand[lm]);
while (res[0] + res[1] != s[lvl]) {
lm--;
if (lm < 0) {
break;
}
res = qry(cand[lm]);
}
if ((lm < 0 ? 0 : res[0]) + rm - lm < i) {
l = rm;
} else {
r = rm;
}
}
pidx.push_back(cand[r]);
}
cand = pidx;
lvl--;
}
return cand[0];
}
