#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> lcache;
vector<int> rcache;
int n;
pair<int,int> askmap(int i){
//cout<<"askmap "<<i<<endl;
if (i>=n){
return {1e9,1e9};
}
assert(i<n);
if (lcache[i]==-1){
vector<int> res = ask(i);
lcache[i] = res[0];
rcache[i] = res[1];
}
return {lcache[i],rcache[i]};
}
int asksum(int i){
auto p = askmap(i);
return p.first+p.second;
}
int find_best(int N) {
n=N;
lcache.resize(n,-1);
rcache.resize(n,-1);
if (n<=600){
for (int i = 0; i < n; i++) {
if(asksum(i) == 0){
return i;
}
}
assert(1==0);
}
int maxsum = 0;
int maxind = -1;
for (int i = 0; i<600; i++){
int res = asksum(i);
if (res==0){return i;}
if (res>maxsum){
maxsum=res;
maxind=i;
}
}
// first ind is at maxind
int ptr = maxind;
while (ptr<n){
//cout<<ptr<<endl;
auto res = askmap(ptr);
if (res.first+res.second==0){return ptr;}
if (res.first+res.second<maxsum){
ptr++;
continue;
}
// otherwise find stretch equal to this value
int l = 0, r = 1;
while (ptr+r<n){
auto rs = askmap(ptr);
if (rs.first+rs.second==0){return ptr;}
if (rs!=res){
break;
}
r<<=1;
}
r=min(r,n-1);
while (l<=r){
int m = (l+r)/2;
if (asksum(ptr+m)==0){return ptr+m;}
if (askmap(ptr+m)!=res){
r=m-1;
} else {
l=m+1;
}
}
ptr+=l;
}
assert(1==0);
return 0;
}
