#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> cache[200005];
vector<int> myask(int x){
if(cache[x].empty())cache[x]=ask(x);
return cache[x];
}
int Maxm[100005];
int find_best(int n) {
int Maxnum=0;
for(int i = 0;i<n&&i<500;i++){
vector<int> v=myask(i);
if(v[0]+v[1]==0)return i;
Maxnum=max(Maxnum,v[0]+v[1]);
}
fill(Maxm,Maxm+n,-1);
int num=0;
while(true){
int Max=n-1,Min=Maxm[num]+1;
// printf("%d %d\n",Max,Min);
while(Max>Min){
int mid=(Max+Min)/2;
vector<int> v=myask(mid);
if(v[0]+v[1]==0)return mid;
if(v[0]<=num){
if(v[0]+v[1]==Maxnum){
Min=mid+1;
}
else{
while(true){
mid++;
v=myask(mid);
if(v[0]+v[1]==0)return mid;
if(v[0]+v[1]==Maxnum){
num=v[0];
Maxm[num]=max(Maxm[num],mid);
break;
}
}
// l=mid+1;
}
}
else if(v[0]+v[1]!=Maxnum){
Max=mid;
}
else{
Maxm[num]=max(Maxm[num],mid);
if(v[0]-num)Max=mid-1;
else Min=mid+1;
}
}
num++;
vector<int> v=myask(Max);
Maxm[num]=max(Maxm[num],Max);
if(v[0]+v[1]==0)return Max;
// printf("? %d %d %d\n",v[0],v[1],num);
// l=Min+1;
}
/*
int Max=n-1,Min=0;
while(Max>Min){
int mid=(Max+Min)/2;
vector<int> v=ask(mid);
if(v[0]+v[1]==0){
return mid;
}
if(v[0]<v[1]){
Min=mid+1;
}
else{
Max=mid-1;
}
}
return Min;*/
}
