#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;
vi myask(int p) {
if (cache.count(p)) return cache[p];
asked++;
return cache[p] = ask(p);
}
int find_best(int n) {
set<int> possible;
int mx = 0;
srand(time(0));
int select;
for (int i = 0;i<100;i++) {
int r = rand()%n;
vi g = myask(r);
if (g[0]+g[1] > mx) {
mx = g[0]+g[1];
select = r;
}
if (g[0]+g[1] == 0) return r;
}
for (int i=0;i<n;i++) possible.insert(i);
int pl = select,pr = select;
while (possible.size() >= 10000-asked) {
if (pl <= 0) break;
vector<int> q = myask(pl);
vi prv = myask(pl-1);
if ((prv[0]+prv[1]) != (q[0]+q[1])) {
int ptr = pl-1;
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 = 0;
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;
}
while (possible.size() >= 10000-asked) {
if (pr >= n-1) break;
vector<int> q = myask(pr);
vi prv = myask(pr+1);
if ((prv[0]+prv[1]) != (q[0]+q[1])) {
int ptr = pr+1;
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 = n-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[0] > q[0])) r = m-1;
else l = m+1;
}
for (int j = pr;j <= r;j++) possible.erase(j);
pr = r;
}
if (possible.size()+asked > 10000) assert(0);
for (auto it : possible) {
vi vv = myask(it);
if (vv[0] + vv[1] == 0) return it;
}
assert(0);
}
