#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],cnt;
int find_best(int n) {
vector <int> ans,lp;
lp.resize(2);
a=n;
for(i=0; i<a+2; i++){
lf[i]=-1;rg[i]=-1;
}
int sq=sqrt(a);
for(i=1; i<=sq+1; i++){
ans=ask(i-1);
cnt++;
if(cnt>=9999){
for(int h=0; ; h++) ;
}
if(ans[0]+ans[1]==0){
return i-1;
}
lf[i]=ans[0];
rg[i]=ans[1];
mx=max(ans[0]+ans[1],mx);
}
for(i=sq+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;
if(lf[mid]==-1){
ans=ask(mid-1);
cnt++;
if(cnt>=9999){
for(int h=0; ; h++) ;
}
}else{
ans[0]=lf[mid];ans[1]=rg[mid];
}
//ans=ask(mid-1);
lf[mid]=ans[0];rg[mid]=ans[1];
if(ans[0]==0&&ans[1]==0){
return mid-1;
}
if(ans[0]==lp[0]&&ans[1]==lp[1]){
lef=mid;
}else{
rig=mid;
pas=mid;
}
}
i=pas;
for(i=i+1; ; i++){
if(lf[i]==-1){
ans=ask(i-1);
cnt++;
if(cnt>=9999){
for(int h=0; ; h++) ;
}
}else{
ans[0]=lf[i];ans[1]=rg[i];
}
//ans=ask(i-1);
lf[i]=ans[0];rg[i]=ans[1];
if(ans[0]+ans[1]==0){
return i-1;
}
if(ans[0]+ans[1]==mx){
break;
}
}
}
}
