#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
int ans=-1,n,lst,sum=0,cnt=0;
vector <int> info[200005];
void ASK(int idx){
//cout<<idx<<endl;
if(info[idx][0]==-1){
info[idx]=ask(idx);
cnt++;
}
if(cnt>=9000) assert(0);
return;
}
void walk(int i){
lst=i;
ASK(i);
if(info[i][0]+info[i][1]==0){
ans=i;
return;
}
if(info[i][0]+info[i][1]==sum){
lst=i;
return;
}
walk(i+1);
return;
}
void search(int i){
ASK(i);
int l=0,r=n-1;
while(l<=r){
int mid=(l+r)/2;
if(mid<i) {l=mid+1;continue;}
ASK(mid);
if(info[mid][0]+info[mid][1]==0){
ans=mid;
return;
}
if(info[mid][0]==info[i][0]&&info[mid][1]==info[i][1]){
lst=mid+1;
l=mid+1;
}
else r=mid-1;
}
return;
}
int find_best(int N) {
srand(time(NULL));
n=N;
for(int i=0;i<n;i++) info[i]={-1,-1};
int k=450;
while(k--){
int idx=rand()%n;
ASK(idx);
if(info[idx][0]+info[idx][1]>sum) sum=info[idx][0]+info[idx][1];
}
while(true){
walk(lst);
if(ans!=-1) return ans;
search(lst);
if(ans!=-1) return ans;
}
return lst;
}
