#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[200005];
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]);
}
int l=0,r=n-1;
int num=0;
while(true){
int Max=r,Min=l;
// 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[1]==0)r=mid-1;
if(v[0]+v[1]!=Maxnum){
Max=mid;
}
else{
Maxm[v[0]]=max(Maxm[v[0]],mid);
if(v[0]-num)Max=mid-1;
else Min=mid+1;
}
}
num++;
Maxm[num]=max(Maxm[num],Max);
vector<int> v=myask(Max);
if(v[0]+v[1]==0)return Max;
// printf("? %d %d %d\n",v[0],v[1],num);
l=Maxm[num]+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;*/
}
