#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
const long long MAXN=200009;
vector<int> ans[MAXN];
int firstLolly=-1;
int lastLolly=-1;
int maxBig=0,used;
inline long long max1(long long a,long long b)
{
if(a>b)return a;
return b;
}
void ask1(int indx)
{
if(ans[indx][0]+ans[indx][1]==0)
{
used++;
//if(used>9990)while(true){};
ans[indx]=ask(indx);
}
}
int rec(int l,int r)
{
//cout<<l<<" "<<r<<endl;
int a,b;
ask1(l);
ask1(r);
if(ans[l][0]==ans[r][0])
{
//cout<<" "<<l<<" "<<r<<endl;
return -1;
}
int mid=(l+r)/2;
ask1(mid);
for(int i=mid;;i--)
{
ask1(i);
if(ans[i][0]+ans[i][1]==0)return i;
if(ans[i][0]+ans[i][1]==maxBig)a=rec(l,i);
}
for(int i=mid;;i++)
{
ask1(i);
if(ans[i][0]+ans[i][1]==0)return i;
if(ans[i][0]+ans[i][1]==maxBig)b=rec(i,r);
}
return max1(a,b);
}
int find_best(int n)
{
for(int i=0;i<n;i++)
{
ans[i].push_back(0);
ans[i].push_back(0);
}
if(n<1000)
{
for(int i=0;i<n;i++)
{
ask1(i);
if(ans[i][0]+ans[i][1]==0)return i;
}
}
for(int i=0;i<480;i++)
{
ask1(i);
if(ans[i][0]+ans[i][1]==0)return i;
if(ans[i][0]+ans[i][1]>maxBig)
{
maxBig=ans[0][i]+ans[i][1];
firstLolly=i;
}
}
for(int i=n-1;;i--)
{
ask1(i);
if(ans[i][0]+ans[i][1]==0)return i;
if(ans[i][0]+ans[i][1]==maxBig)
{
lastLolly=i;
break;
}
}
return rec(firstLolly,lastLolly);
}
