#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 myask(int p) {
if (cache.count(p)) return cache[p];
asked++;
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;
}
}
int pr = select;
for (int i = select+1;i<n;i++) possible.insert(i);
while (asked < 5500) {
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;
possible.erase(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+450);
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;
}
vi v(all(possible));
shuffle(all(v),mt19937_64(0));
for (auto it : v) {
vi vv = myask(it);
if (vv[0] + vv[1] == 0) return it;
}
assert(0);
}
