#include "prize.h"
#include <bits/stdc++.h>
//#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
using namespace std;
const int inf = 2e9;
map<int,vi> cache;
int asked = 0;
set<int> possible;
vi askeys;
vi myask(int p) {
if (cache.count(p)) return cache[p];
asked++;
askeys.push_back(p);
cache[p] = ask(p);
if (cache[p][0]+cache[p][1]) possible.erase(p);
return cache[p];
}
int find_best(int n) {
int mx = 0;
srand(time(0));
int select;
for (int i = 0;i<500 && i<n;i++) {
vi v = myask(i);
if (v[0]+v[1] == 0) return i;
if (v[0]+v[1] > mx) {
mx = v[0]+v[1];
select = i;
}
}
for (int i=0;i<select;i++) possible.insert(i);
for (auto it : askeys) {
vi vvv = myask(it);
if (vvv[0]+vvv[1]) possible.erase(it);
else return it;
}
possible.clear();
int pl = select,pr = select;
while (possible.size()+asked > 4800) {
if (pl <= 0) break;
vector<int> q = myask(pl);
vi prv = myask(pl-1);
if (prv[0]+prv[1] == 0) return pl-1;
if ((prv[0]+prv[1]) != (q[0]+q[1])) {
int ptr = pl-1;
possible.erase(ptr);
while (ptr > 0) {
prv = myask(ptr-1);
if (prv[0]+prv[1] == 0) return ptr-1;
if ((prv[0]+prv[1]) != (q[0]+q[1])) ptr--;
else break;
}
pl = ptr-1;
continue;
}
int l = max(0,pl-500);
int r = pl-1;
while (l<=r) {
int m = (l+r) >> 1;
vi vv = myask(m);
if (vv[0]+vv[1] == 0) return m;
if ((vv[0]+vv[1] != q[0]+q[1]) || (vv[1] > q[1])) l = m+1;
else r = m-1;
}
for (int j = pl;j >= l;j--) possible.erase(j);
pl = l;
}
vi v;
for (auto it : possible) v.push_back(it);
shuffle(all(v),mt19937_64(0));
for (auto it : v) {
vi vv = myask(it);
if (vv[0] + vv[1] == 0) return it;
}
possible.clear();
for (int i = select+1;i<n;i++) possible.insert(i);
for (auto it : askeys) {
vi vvv = myask(it);
if (vvv[0]+vvv[1]) possible.erase(it);
else return it;
}
while (possible.size()+asked > 4800) {
if (pr >= n-1) break;
vector<int> q = myask(pr);
vi prv = myask(pr+1);
if (prv[0]+prv[1] == 0) return pr+1;
if ((prv[0]+prv[1]) != (q[0]+q[1])) {
int ptr = pr+1;
possible.erase(ptr);
while (ptr < n-1) {
prv = myask(ptr+1);
if (prv[0]+prv[1] == 0) return ptr+1;
if ((prv[0]+prv[1]) != (q[0]+q[1])) ptr++;
else break;
}
pr = ptr+1;
continue;
}
int l = pr+1;
int r = min(n-1,pr+500);
while (l<=r) {
int m = (l+r) >> 1;
vi vv = myask(m);
if (vv[0]+vv[1] == 0) return m;
if ((vv[0]+vv[1] != q[0]+q[1]) || (vv[0] > q[0])) r = m-1;
else l = m+1;
}
for (int j = pr;j <= r;j++) possible.erase(j);
pr = r;
}
v.clear();
for (auto it : possible) if (it > select) v.push_back(it);
shuffle(all(v),mt19937_64(0));
for (auto it : v) {
vi vv = myask(it);
if (vv[0] + vv[1] == 0) return it;
}
assert(0);
}
