#include<iostream>
#include"prize.h"
using namespace std;
typedef long long ll;
int find_best(int n){
vector<int> a,b,v;
int bef=-1;
int ma=-1;
for(int i=0;i<min(n,450);i++){
a=ask(i);
int t=a[0]+a[1];
if(t==0)return i;
if(t>ma){
ma=t;
}
}
for(int i=0;i<min(n,450);i++){
a=ask(i);
int t=a[0]+a[1];
if(t!=ma){
bef=i;
break;
}
}//はじめての上が見つかるorすべてアメ
while(1){
b=ask(bef+1); if(b[0]+b[1]==0)return bef+1;
if(b[0]+b[1]!=ma){
bef=bef+1;
continue;
}
ll l=bef+1,r=n-1,mid;
while(l<r-1){
mid=(l+r)>>1;
a=ask(mid);
if(a[0]+a[1]==ma){
if(a==b)l=mid;
else r=mid;
}
else{
r=mid;
}
}
bef=r;
b=ask(r); if(b[0]+b[1]==0)return r;
}
}
