#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;
void ask1(int indx)
{
if(ans[indx][0]+ans[indx][1]==0)
{
used++;
if(used>9990)while(true){};
ans[indx]=ask(indx);
}
}
int binaryS(int l,int r,int v)
{
int mid;
while(l+1<r)
{
mid=(l+r)/2;
ask1(mid);
if(ans[mid][0]+ans[mid][1]!=maxBig||ans[mid][0]>v)
{
r=mid-1;
}
else
{
l=mid;
}
}
ask1(r);
if(ans[r][0]==v&&ans[r][0]+ans[r][1]==maxBig)return r;
return l;
}
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<450;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;
}
}
while(true)
{
firstLolly=binaryS(firstLolly,lastLolly,ans[firstLolly][0])+1;
for(;;firstLolly++)
{
ask1(firstLolly);
if(ans[firstLolly][0]+ans[firstLolly][1]==maxBig)break;
if(ans[firstLolly][0]+ans[firstLolly][1]==0)return firstLolly;
}
}
return -1;
}
