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