#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 = 450;
vector<int> que[maxn];
int cnt_asks;
vector<int> abc(int i) {
if(!que[i].empty()) {
return que[i];
} else {
++cnt_asks;
return que[i] = ask(i);
}
}
int find_best(int n) {
int mx = 0;
for(int ite = 0; ite < 25; ++ite) {
int p = rand(0, n - 1);
vector<int> cur_ask = abc(p);
mx = max(mx, cur_ask[0] + cur_ask[1]);
}
int ptr = 0;
abc(ptr);
if (que[ptr][0] + que[ptr][1] == 0) return ptr;
while (ptr < n) {
while (ptr < n) {
vector<int> xx = abc(ptr);
if (xx[0] + xx[1] == 0) return ptr;
if (xx[0] + xx[1] == mx) break;
++ptr;
}
// debug(ptr);
int x = min(n - 1, ptr + B);
while (x > ptr) {
vector<int> cur = abc(x);
if (cur[0] + cur[1] == 0) return x;
if (cur[0] + cur[1] < mx) --x;
else break;
}
if (x == ptr) {
ptr += B + 1;
continue;
}
vector<int> cur = abc(x);
vector<int> cur_ask = abc(ptr);
// debug(x, cur);
if (cur[0] - cur_ask[0]) {
int l = ptr + 1, r = n - 1, nxt = ptr;
while(l <= r) {
int mid = (l + r) >> 1;
vector<int> he = abc(mid);
if(he == cur_ask) {
nxt = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
ptr = nxt + 1;
} else {
ptr = x;
}
}
int spec = 0;
return -1;
}
