#include<bits/stdc++.h>
#include "prize.h"
using namespace std;
bool asked[200005];
int otgv[200005][2];
vector<int> ask2(int pos)
{
vector<int> anst;
if(asked[pos]) {anst.push_back(otgv[pos][0]); anst.push_back(otgv[pos][1]); return anst;}
asked[pos]=1;
anst=ask(pos);
otgv[pos][0]=anst[0];
otgv[pos][1]=anst[1];
return anst;
}
bool findans=0;
int pos=0, brask=0;
int maxsum=0;
void solve(int le, int ri, int bal_le, int bal_ri, int br)
{
if(le>ri || !br) return;
int mid=(le+ri)/2;
vector<int> res=ask2(mid);
if(res[0] + res[1] == 0)
{
findans=1;
pos=mid;
return;
}
if(res[0]+res[1]==maxsum)
{
solve(le, mid-1, bal_le, res[1], res[0]-bal_le);
if(findans) return;
solve(mid+1, ri, res[0], bal_ri, res[1]-bal_ri);
return;
}
int m2=mid;
while(m2-1>=le && res[0]+res[1]!=maxsum)
{
m2--;
res=ask2(m2);
/// cout<<m2<<endl;
if(res[0] + res[1] == 0)
{
findans=1;
pos=m2;
return;
}
}
if(m2==le && res[0]+res[1]<maxsum) solve(mid+1, ri, bal_le+mid-le+1, bal_ri, br-mid+le-1);
else
{
solve(le, m2, bal_le, res[1], res[0]-bal_le);
if(findans) return;
solve(mid+1, ri, maxsum-bal_ri-(br-(res[0]-bal_le)-(mid-m2)), bal_ri, br-(res[0]-bal_le)-(mid-m2));
}
}
int find_best(int n)
{
for(int i = 0; i <450; i++)
{
vector<int> res = ask2(i);
if(res[0] + res[1] == 0) return i;
if(res[0]+res[1]>maxsum) maxsum=res[0]+res[1];
}
solve(0, n-1, 0, 0, maxsum);
return pos;
}
