#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;
vector<int> cnt(5);
vector<int> tar, cand;
void dfs(int l, int r, int cnt) {
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] < cnt) {
tar.push_back(cand[lm]);
lm--;
if (lm < l) {
break;
}
res = qry(cand[lm]);
}
int lc = res[0], rc = res[1] - (rm - lm);
if (lc > 0) {
dfs(l, lm - 1, lc);
}
if (rc > 0) {
dfs(lm + 1, r, rc);
}
}
}
int find_best(int n) {
buf.clear(), buf.resize(n);
for (int i = 0; i < min(n, 447); i++) {
vector<int> res = qry(i);
cnt[0] = max(cnt[0], res[0] + res[1]);
}
for (int i = 0; i < n; i++) {
cand.push_back(i);
}
while (cand.size() > 1) {
dfs(0, n - 1, cnt[0]);
cand = tar;
}
return cand[0];
}
