/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
typedef long long ll;
vector <int> ask (int i);
vector <int> L, R;
void discover (int i) {
vector <int> resp = ask(i);
L[i] = resp[0];
R[i] = resp[1];
}
int getL (int i) {
if (L[i] == -1) {
discover(i);
}
return L[i];
}
int getR (int i) {
if (R[i] == -1) {
discover(i);
}
return R[i];
}
int getLR (int i) {
return getL(i) + getR(i);
}
vector <int> findLess (vector <int> v) {
int cntLess = 0;
int k = 25;
while (k--) {
int i = v[rand() % (int) v.size()];
cntLess = max(cntLess, getLR(i));
}
vector <int> vless;
while (true) {
int lo = (vless.empty() == true ? 0 : vless.back() + 1);
int hi = (int) v.size();
while (lo < hi) {
int mid = (lo + hi) / 2;
if (getLR(v[mid]) != cntLess) {
hi = mid;
} else if (getL(v[mid]) > (int) vless.size()) {
hi = mid;
} else {
lo = mid + 1;
}
}
if (lo < (int) v.size()) {
vless.push_back(lo);
} else {
break;
}
}
for (int &x : vless) {
x = v[x];
}
return vless;
}
int find_best (int n) {
L = vector <int> (n, -1);
R = vector <int> (n, -1);
vector <int> v (n);
iota(v.begin(), v.end(), 0);
while ((int) v.size() > 1) {
v = findLess(v);
}
return v.front();
}
