#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> buf;
vector<int> qry(int x) {
if (buf[x].empty()) {
return buf[x] = ask(x);
} else {
return buf[x];
}
}
int level, lvcnt[5];
vector<int> tar, cand;
void dfs(int l, int r, int cnt, int lp, int rs) {
if (l == r) {
tar.push_back(cand[l]);
} else {
int rm = l + (r - l) / 2, lm = rm;
vector<int> res = qry(cand[lm]);
while (res[0] + res[1] < lvcnt[level]) {
tar.push_back(cand[lm]);
lm--;
if (lm < l) {
break;
}
res = qry(cand[lm]);
}
int lc = res[0] - lp;
if (lc > 0) {
dfs(l, lm - 1, lc, lp, res[1]);
}
lm = rm;
res = qry(cand[lm]);
while (res[0] + res[1] < lvcnt[level]) {
tar.push_back(cand[lm]);
lm++;
if (lm > r) {
break;
}
res = qry(cand[lm]);
}
int rc = res[1] - rs;
if (rc > 0) {
dfs(lm + 1, r, rc, res[0], rs);
}
}
}
int find_best(int n) {
buf.clear(), buf.resize(n);
for (int i = 0; i < n; i++) {
cand.push_back(i);
}
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 = int(sqrt(t));
sum += t;
}
if (sum <= cand.size()) {
l = m;
} else {
r = m;
}
}
for (int i = 0; i < r - 10; i++) {
vector<int> res = qry(cand[i]);
lvcnt[level] = max(lvcnt[level], res[0] + res[1]);
}
tar.clear();
dfs(0, cand.size() - 1, lvcnt[level], 0, 0);
sort(tar.begin(), tar.end());
tar.resize(unique(tar.begin(), tar.end()) - tar.begin());
cand = tar;
level++;
}
return cand[0];
}
