#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,lef,rig,mid,T=550,BO[200009],mx,E;
pair <int, int> P[200009];vector <int> vv;
void ASK(int q){
if(BO[q]==0){
BO[q]=1;vv=ask(q-1);
P[q]=make_pair(vv[0],vv[1]);
}
}
int find_best(int Nn) {
a=Nn;
for(i=1; i<=min(T,a); i++){
ASK(i);
mx=max(mx,P[i].first+P[i].second);
}
ASK(a);i=0;
E=P[a].first;
while(1){
if(i>=a||P[i].first==E) break;
lef=i;rig=a+1;
while(1){
if(lef+1>=rig) break;
mid=(lef+rig)/2;
ASK(mid);j=mid;
while(P[j].first+P[j].second!=mx){
j--;ASK(j);
}
if(P[j].first==P[i].first){
lef=mid;
}else{
rig=mid;
}
}
//rig-1 > lollipop
ASK(rig-1);
i=rig;ASK(i);
while(i<a&&P[i].first+P[i].second!=mx){
i++;ASK(i);
}
}
for(i=1; i<=a; i++){
if(BO[i]!=0&&P[i].first==0&&P[i].second==0){
return i-1;
}
}
return 0;
}
