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