#include "prize.h"
#include "bits/stdc++.h"
using namespace std;
#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
assert(l <= r);
return uniform_int_distribution<int> (l, r)(rng);
}
const int maxn = 2e5 + 5;
const int B = 480;
vector<int> que[maxn];
int cnt_asks;
vector<int> abc(int i) {
++cnt_asks;
if(!que[i].empty()) {
return que[i];
} else {
return que[i] = ask(i);
}
}
int ans, mx;
void calc(int l, int r) {
if (l >= r || ans != -1) return;
if (que[r][0] - que[l][0] == 0) return;
int mid = (l + r) >> 1;
vector<int> cm = abc(mid);
int pl = mid, pr = mid;
while (pr < r) {
abc(pr);
if (que[pr][0] + que[pr][1] == 0) {
ans = pr;
return;
}
if (que[pr][0] + que[pr][1] == mx) break;
++pr;
}
while (pl > l) {
abc(pl);
if (que[pl][0] + que[pl][1] == 0) {
ans = pl;
return;
}
if (que[pl][0] + que[pl][1] == mx) break;
--pl;
}
calc(l, pl);
calc(pr, r);
}
int find_best(int n) {
vector<int> prf(n);
iota(prf.begin(), prf.end(), 0);
shuffle(prf.begin(), prf.end(), rng);
for (int ite = 0; ite < min(20, (int)prf.size()); ++ite) {
int p = prf[ite];
abc(p);
mx = max(mx, que[p][0] + que[p][1]);
}
ans = -1;
int x = 0;
while (x < n) {
abc(x);
if (que[x][0] + que[x][1] == mx) break;
++x;
}
int lst = n - 1;
while (lst >= 0) {
vector<int> cur = abc(lst);
if (cur[0] + cur[1] == 0) return lst;
if (cur[0] + cur[1] == mx) break;
--lst;
}
calc(x, lst);
return ans;
}
