#include<bits/stdc++.h>
#include "prize.h"
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,sq,lef,rig,mid,pas,mx,lf[200009],rg[200009];
int find_best(int n) {
vector <int> ans,lp;
lp.resize(2);
a=n;
for(i=1; i<=450; i++){
ans=ask(i-1);
if(ans[0]+ans[1]==0){
return i;
}
lf[i]=ans[0];
rg[i]=ans[1];
mx=max(ans[0]+ans[1],mx);
}
for(i=1; ; i++){
if(lf[i]+rg[i]==mx) break;
}
while(1){
lef=i;rig=a+1;
lp[0]=lf[i];lp[1]=rg[i];
pas=0;
while(1){
if(lef+1>=rig) break;
mid=(lef+rig)/2;
ans=ask(mid-1);
lf[mid]=ans[0];rg[mid]=ans[1];
if(ans[0]==0&&ans[1]==0){
return mid;
}
if(ans[0]==lp[0]&&ans[1]==lp[1]){
rig=mid;
pas=mid;
}else{
lef=mid;
}
}
for(i=i+1; ; i++){
ans=ask(i-1);
lf[i]=ans[0];rg[i]=ans[1];
if(ans[0]+ans[1]==0){
return i;
}
if(ans[0]+ans[1]==mx){
break;
}
}
}
}
