#include "prize.h"
#ifdef NYAOWO
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
// #define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;
const int MAXN = 200'000;
mt19937_64 rng(48763);
pii mem[MAXN + 10];
pii qry(int idx) {
if(mem[idx].F != -1) return mem[idx];
auto res = ask(idx);
return mem[idx] = pii(res[0], res[1]);
}
int solve(vector<int> v) {
if(sz(v) == 1) return v[0];
int len = sz(v);
// int tot = 0;
// For(_, 1, 5) {
// pii p = qry(v[rng() % len]);
// tot = max(tot, p.F + p.S);
// }
int tot = 1;
vector<int> res;
For(i, 0, tot - 1) {
int lo, hi = len;
if(!sz(res)) lo = -1;
else lo = res.back();
while(hi - lo > 1) {
int mi = (hi + lo) / 2;
pii p = qry(v[mi]);
if(p.F + p.S < tot || p.F > i) hi = mi;
else lo = mi;
}
assert(hi < len);
res.eb(hi);
}
return solve(res);
}
i32 find_best(i32 n) {
fill(mem, mem + MAXN + 10, pii(-1, -1));
vector<int> v(n);
For(i, 0, n - 1) v[i] = i;
return solve(v);
}
