/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
#pragma GCC optimize ("unroll-loops")
using namespace std;
typedef long long ll;
vector <int> ask (int i);
vector <int> L, R;
void discover (int i) {
if (L[i] == -1) {
vector <int> resp = ask(i);
L[i] = resp[0];
R[i] = resp[1];
}
}
mt19937 rnd (time(0));
vector <int> findLess (const vector <int> &v) {
int cntLess = 0;
for (int k = 0; k < (int) sqrt((int) v.size()); k++) {
int i = v[k]; discover(i);
cntLess = max(cntLess, L[i] + R[i]);
}
vector <int> vless;
while ((int) vless.size() < cntLess) {
int lo = (vless.empty() == true ? 0 : vless.back() + 1);
int hi = (int) v.size();
while (lo < hi) {
int mid = (lo + hi) / 2;
int i = v[mid]; discover(i);
if (L[i] + R[i] != cntLess) {
hi = mid;
} else if (L[i] > (int) vless.size()) {
hi = mid;
} else {
lo = mid + 1;
}
}
vless.push_back(lo);
}
for (int &x : vless) {
x = v[x];
}
assert((int) vless.size() < (int) v.size());
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();
}
