#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 rng(time(NULL));
pii mem[MAXN + 10];
int qry_cnt = 0;
pii qry(int idx) {
if(mem[idx].F != -1) return mem[idx];
qry_cnt++;
auto res = ask(idx);
return mem[idx] = pii(res[0], res[1]);
}
int solve(int n) {
int tot = 0;
For(_, 1, 100) {
pii p = qry((int)(rng() % (LL)n));
tot = max(tot, p.F + p.S);
}
vector<int> res;
bool fail = true;
while(fail) {
fail = false;
res.clear();
priority_queue<pii, vector<pii>, greater<pii>> pq;
For(i, 0, tot - 1) {
int lo, hi = n;
if(!sz(res)) lo = -1;
else lo = res.back();
while(sz(pq) && pq.top().F < i) pq.pop();
while(sz(pq) && pq.top().F == i) {
lo = max(lo, pq.top().S);
pq.pop();
}
if(sz(pq)) {
assert(pq.top().F > i);
hi = pq.top().S;
}
while(hi - lo > 1) {
int mi = (hi + lo) / 2;
pii p = qry(mi);
if(p.F + p.S > tot) {
fail = true;
tot = p.F + p.S;
goto FAIL;
}
if(p.F + p.S < tot || p.F > i) hi = mi;
else lo = mi;
if(p.F + p.S == tot) pq.emplace(p.F, mi);
}
assert(hi < n);
res.eb(hi);
}
FAIL:;
}
for(auto &i:res) {
pii p = qry(i);
if(p.F + p.S == 0) {
assert(qry_cnt <= 4500);
return i;
}
}
return -8;
}
i32 find_best(i32 n) {
fill(mem, mem + MAXN + 10, pii(-1, -1));
#ifndef NYAOWO
if(n <= 5000) {
For(i, 0, n - 1) {
pii p = qry(i);
if(p.F + p.S == 0) return i;
}
return -8;
}
#endif
return solve(n);
}
