#include "prize.h"
#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define all(x) x.begin(), x.end()
#define ceil(a, b) ((a + b - 1) / (b))
#define big 4172398721
#define MOD 1000000007
using namespace std;
#define pii pair<int, int>
#ifdef wiwihorz
#define print(a...) cerr << "Line: " << __LINE__, kout("[" + string(#a) + "] = ", a)
void vprint(auto L, auto R) { while(L < R)cerr << *L << " \n"[next(L) == R], ++L; }
void kout() { cerr << endl; }
template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...);}
#else
#define print(...) 0
#define vprint(...) 0
#endif
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())
int x;
random;
map<int, pii> mp;
pii Ask(int x) {
if(mp.find(x) == mp.end()) {
vector<int> v;
v = ask(x);
mp[x] = {v[0], v[1]};
}
return mp[x];
}
int solve(int L, int R, int tot, int pre) {
// print(L, R, tot, pre);
if(L == R) {
pii p = Ask(L);
return (p.first + p.second ? -1 : L);
}
int mid = (L + R) / 2, piv = -1, ans = -1;
rep(i, mid + 1, R) {
pii p = Ask(i);
if(p.first + p.second == x) {
piv = i;
break;
}
else ans = max(ans, solve(i, i, 1, 0));
}
if(piv < 0) ans = (tot - (R - mid) ? max(ans, solve(L, mid, tot - (R - mid), pre)) : ans);
else {
pii p = Ask(piv);
int left = p.first - pre - (piv - mid - 1);
int right = tot - p.first + pre;
if(left) ans = max(ans, solve(L, mid, left, pre));
if(right) ans = max(ans, solve(piv, R, right, p.first));
}
return ans;
}
int find_best(int n) {
x = 0;
vector<pii> s;
rrep(i, 0, n - 1) s.push_back({big * rnd() % MOD, i});
sort(all(s));
rep(i, 0, min(473, n) - 1) {
pii p = Ask(s[i].second);
x = max(x, p.first + p.second);
}
return solve(0, n - 1, x, 0);
}
