#include<bits/stdc++.h>
#include "prize.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int pos,minr,limt;
map<int,pii> dic;
pii query(int p){
if(dic.size()==9999) assert(false);
if(dic.find(p)!=dic.end()) return dic[p];
vector<int> q=ask(p);
return dic[p]=pii(q[0],q[1]);
}
void solve(int l,int r){
if(pos!=-1) return;
if(l==r){
pii q=query(l);
if(q.first==0 && q.second==0) pos=l;
else if(q.first+q.second==limt) minr=min(minr,q.second);
}else{
int mid=(l+r)>>1;
pii q=query(mid+1);
if(q.first+q.second<limt || q.second>minr) solve(mid+1,r);
solve(l,mid);
}
}
int find_best(int n){
srand(time(nullptr));
for(int i=0;i<10;i++){
int p=rand()%n;
pii q=query(p);
limt=max(limt,q.first+q.second);
}
minr=pos=-1;
solve(0,n-1);
return pos;
}
