#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+6;
pair<int,int> answer[MAXN];
vector<int>valuable;
int maxs=0;
pair<int,int>q;
vector<int>lollipops;
char lorv[MAXN];
pair<int,int> get_answer(int i)
{
if(answer[i].first!=-1)return answer[i];
vector<int>q=ask(i);
answer[i].first=q[0];
answer[i].second=q[1];
return answer[i];
}
void bs(int l,int r)
{
if(l>r)return;
pair<int,int> ivan=get_answer(l);
if(l==r)
{
if(ivan.first+ivan.second!=maxs)
{
valuable.push_back(l);
}
return;
}
if(ivan.first+ivan.second!=maxs)
{
valuable.push_back(l);
bs(l+1,r);
return;
}
int mid,low=l,high=r,ans=-1;
while(low<=high)
{
mid=(low+high)/2;
ivan=get_answer(mid);
if(ivan.first+ivan.second!=maxs)
{
ans=mid;
break;
}
if(ivan.first>get_answer(l).first)
{
high=mid-1;
}
else low=mid+1;
}
if(ans==-1)return;
valuable.push_back(ans);
bs(l+1,ans-1);
bs(ans+1,r);
}
int find_best(int n) {
if(n<=5000)
{
for(int i=0;i<n;i++)
{
vector<int>t=ask(i);
if(t[0]+t[1]==0)
{
return i;
}
}
}
for(int i=0;i<n;i++)answer[i]={-1,-1};
for(int i=0;i<500;i++)
{
q=get_answer(i);
if(q.first+q.second==0)
{
return i;
}
answer[i]=q;
maxs=max(maxs,q.first+q.second);
}
bs(0,n-1);
/*for(int i=0;i<n;i++)lorv[i]='?';
for(int i=0;i<500;i++)
{
if(answer[i].first+answer[i].second==maxs)
{
lorv[i]='L';
lollipops.push_back(i);
}
else
{
lorv[i]='V';
valuable.push_back(i);
}
}
bs(500,n-1);*/
for(auto j:valuable)
{
if(get_answer(j).first+get_answer(j).second==0)
{
return j;
}
}
assert(false);
return 0;
}
