#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> cache[200005];
int Maxnum=0;
int cnt=0;
vector<int> myask(int x){
if(cache[x].empty()){
cache[x]=ask(x);
if(cache[x][0]+cache[x][1]==Maxnum)cnt++;
//printf("%d\n",x);
}
return cache[x];
}
int Maxm[200005];
bool cal(int l,int r,int Maxnum,int num,int &res){
if(l>r)return false;
int mid=(l+r)/2;
int a=mid,b=mid;
while(true){
if(a<l)break;
vector<int> v=myask(a);
if(v[0]+v[1]==0){res=a;return true;}
if(v[0]+v[1]==Maxnum){
break;
}
a--;
}
while(true){
if(b>r)break;
vector<int> v=myask(b);
if(v[0]+v[1]==0){res=b;return true;}
if(v[0]+v[1]==Maxnum){
break;
}
b++;
}
vector<int> v=myask(a);
if(v[0]!=num){
assert(v[0]>num);
if(cal(l,a-1,Maxnum,num,res))return true;
num=v[0];
}
v=myask(b);
if(cal(b+1,r,Maxnum,v[0],res))return true;
return false;
}
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 res;
cal(0,n-1,Maxnum,0,res);
printf("%d\n",cnt);
return res;
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;*/
}
/*
1 2 5 447 90001
*/
