#include "prize.h"
#include <bits/stdc++.h>
#define forn(i,a,b) for(int i = a; i<b; i++)
using namespace std;
typedef long long ll;
map<int,vector<int>> ret;
map<int,bool> isq;
ll cnt = 0;
vector<int> aask(int i ){
if(isq[i]) return ret[i];
isq[i]=true;
ret[i]=ask(i);
cnt++;
/* while(cnt>9990){
exit(0);
}*/
//cout<<cnt<<'\n';
return ret[i];
}
int find_best(int n) {
srand(time(NULL));
ll i = 0;
vector<int> ares = {-1,-1};
vector<int> last = {-1,-1};
forn(i,0,min(472,n)){
vector<int> res = aask(i);
if(res[0]+res[1]>last[0]+last[1]) last=res;
}
ll rng = 0;
vector<ll> pj; forn(j,0,301) pj.push_back(j);
forn(k,0,301){
ll rj = rand()%(int(pj.size()));
int j = pj[rj];//pj[rj];
i=j*(667);
ll nmax = min(n,j*667+667);
ares={-1,-1};
while(i<nmax){
vector<int> ires = ares;
ires=aask(i);
if(ires[0]==0 && ires[1]==0) return i;
if(ires[0]+ires[1]!=last[0]+last[1]){
i++;
continue;
}
rng++;
ll l = i+1; ll r=nmax-1;
vector<int> rv = aask(r);
if(rv[0]==ires[0] && rv[0]+rv[1]==ires[0]+ires[1]){ break; }
if(rv[0]+rv[1]==ires[0]+ires[1]) r--;
while(l<=r){
ll mid=(l+r)/2;
vector<int> res = aask(mid);
ares=res;
//cout<<res[1]<<" <-"<<mid<<'\n';
if(res[1]<ires[1]||res[1]+res[0]!=ires[1]+ires[0]) r=mid-1;
else l=mid+1;
}
i=r+1;
//cout<<"rango "<<rng<<'\n';
}
pj.erase(pj.begin()+rj);
//cout<<"tam "<<(int)pj.size()<<'\n';
}
cout<<"salio\n";
return 0;
}
