#include<bits/stdc++.h>
#include "prize.h"
using namespace std;
bool findans=0;
int pos=0;
int maxsum=0;
void solve(int le, int ri, int bal_le, int bal_ri, int br)
{
///cout<<le<<" "<<ri<<endl;
if(le>ri || !br) return;
int mid=(le+ri)/2;
vector<int> res=ask(mid);
///cout<<mid<<endl;
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);
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=ask(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);
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 < 500 && i<n; i++)
{
vector<int> res = ask(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;
}
