#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> memoiz[200005];
vector<int> customAsk(int x){
// Memoized version of ask
if(memoiz[x].empty()) return memoiz[x] = ask(x);
else return memoiz[x];
}
int solve(int l, int r, int offsL, int offsR){
if(l == r) return -1;
int m = (l+r)/2;
vector<int> res = customAsk(m);
if(res[0] + res[1] == 0) return m;
int left = -1;
if(res[0] - offsL > 0) left = solve(l, m-1, offsL, res[1]);
if(left != -1) return left;
if(res[1] - offsR > 0) return solve(m+1, r, res[0], offsR);
return -1;
}
int find_best(int n) {
if(n < 5000){
for(int i = 0; i < n; i++) {
vector<int> res = customAsk(i);
if(res[0] + res[1] == 0)
return i;
}
}
int b = sqrt(n);
vector<tuple<int,int,int,int> > eachBlock; // (L, R, offsL, offsR)
int last = 0;
int lidx = -1;
for(int i = b; i < n;){
vector<int> cur = customAsk(i);
if(cur[0] + cur[1] <= 2*b){
i++;
}else{
eachBlock.emplace_back(lidx+1, i, last, cur[1]);
last = cur[0];
lidx = i;
i += b;
}
}
if(lidx != n-1) eachBlock.emplace_back(lidx+1, n-1, last, 0);
for(auto block : eachBlock){
int l,r,ofl,ofr;
tie(l,r,ofl,ofr) = block;
int ret = solve(l, r, ofl, ofr);
if(ret != -1) return ret;
}
return 0;
}
