#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 level, lvcnt[5];
vector<int> tar, cand;
void dfs(int l, int r, int cnt, int lp, int rs) {
if (r - l + 1 == cnt) {
for (int i = l; i <= r; i++) {
tar.push_back(cand[i]);
}
} else {
int rm = l + (r - l) / 2;
vector<int> res = qry(cand[rm]);
if (res[0] + res[1] == lvcnt[level]) {
if (res[0] - lp > 0) {
dfs(l, rm - 1, res[0] - lp, lp, res[1]);
}
if (res[1] - rs > 0) {
dfs(rm + 1, r, res[1] - rs, res[0], rs);
}
} else {
int lm = rm;
while (res[0] + res[1] < lvcnt[level]) {
tar.push_back(cand[lm]);
lm--;
if (lm < l) {
break;
}
res = qry(cand[lm]);
}
if (lm >= l) {
int lc = res[0] - lp;
if (lc > 0) {
dfs(l, lm - 1, lc, lp, res[1]);
}
int rc = res[1] - rs - (rm - lm);
if (rc > 0) {
dfs(rm + 1, r, rc, res[0] + (rm - lm), rs);
}
} else {
int 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 lc = res[0] - lp - (lm - rm);
if (lc > 0) {
dfs(l, rm - 1, lc, lp, res[1] - (rm - 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 u = 0;
while (true) {
int t = u, sum = t * t + t + 1;
while (t > 1) {
t = sqrt(t);
sum += t;
}
if (sum > cand.size()) {
u--;
break;
}
u++;
}
int lim = 1, t = u;
while (t > 1) {
lim += t;
t = sqrt(t);
}
for (int i = 0; i < lim; 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];
}
