#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> vv;
vector<int> ask2(int x){
if(vv[x].empty()){
vv[x]=ask(x);
}
return vv[x];
}
int find_best(int n) {
vv.resize(n);
vector<int> v;
int mx=-1,id;
for(int i=0;i<min(n,500);i++){
auto t=ask2(i);
if(t[0]+t[1]>mx){
mx=t[0]+t[1];
id=i;
}
if(mx>35)break;
}
for(int i=0;i<id;i++){
v.push_back(i);
}
int z=300,l2=id;
while(v.size()<mx){
int l=l2,r=min(n,l+z);
{
auto t=ask2(r-1);
if(t[0]+t[1]==mx&&t[0]==v.size()){
l2+=z;
continue;
}
}
int t=r;
while(l<r){
int m=l+r>>1;
auto t=ask2(m);
if(t[0]+t[1]<mx||t[0]>v.size())r=m;
else l=m+1;
}
assert(l<t);
v.push_back(l);
l2=l+1;
}
for(int i:v){
auto t=ask2(i);
if(t[0]+t[1]==0)return i;
}
return -1;
}
