#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=323,cc=0;
while(v.size()<mx){
int rr,l,r;
cc--;
do{
cc++;
rr=min(n-1,(cc+1)*z),l=cc*z,r=rr+1;
if(!v.empty())l=max(l,v.back()+1);
}while(l>=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;
}
if(l==rr+1){
cc++;
}
v.push_back(l);
}
for(int i:v){
auto t=ask2(i);
if(t[0]+t[1]==0)return i;
}
return -1;
}
