#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
pair<int,int> memo[200005];
set<pair<int,int> > s;
pair<int,int> qry(int x){
if(memo[x].first!=-1)return memo[x];
vector<int> v=ask(x);
s.insert(make_pair(v[0],x));
return memo[x]=make_pair(v[0],v[1]);
}
int find(int x){
auto it=s.lower_bound(make_pair(x,-1));
return it->second;
}
int find_best(int n){
for(int i=0;i<n;i++)memo[i]=make_pair(-1,-1);
int k=1;
while(k*(k+1)<n)k++;
int sz=0;
for(int i=0;i<=k;i++){
pair<int,int> p=qry(i);
sz=max(sz,p.first+p.second);
}
for(int start=0;start<=k;start++){
pair<int,int> p=qry(start);
if(p.first+p.second==sz){
int ans=start;
while(ans<n){
p=qry(ans);
if(p.first+p.second==sz){
int l=ans,r=find(p.first+1)-1; // rightmost thing with the same p
pair<int,int> p2;
while(l<r){
int mid=(l+r+1)/2;
p2=qry(mid);
if(p2==p){
l=mid;
}else{
r=mid-1;
}
}
ans=l+1;
}else{
if(p.first==0&&p.second==0)break;
ans++;
}
}
return ans;
}else if(p.first==0&&p.second==0){
return start;
}
}
return n;
}
/*
8
3 2 3 1 3 3 2 3
*/
