#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];
}
ll calc(ll l , ll r){
if(l==r-1){
// cout<<aask(l)[0]<<" <-> "<<aask(l)[1]<<'\n';
if(aask(l)[0]==aask(l)[1]&&aask(l)[0]==0) return l;
if(aask(r)[0]==aask(r)[1]&&aask(r)[0]==0) return r;
return -1;
}
if(aask(l)[0]==aask(r)[0] && aask(l)[1]==aask(r)[1]) return -1;
ll mid = (l+r)/2;
ll prl = calc(l,mid);
if(prl>-1) return prl;
ll prr = calc(mid,r);
return max(prl,prr);
}
int find_best(int n) {
srand(time(NULL));
ll i = 0;
vector<int> ares = {-1,-1};
vector<int> last = {-1,-1};
forn(j,0,392){
i=j*(512);
ll nmax = min(n,j*512+512);
if(i>=nmax) break;
aask(i);
aask(nmax-1);
}
i=0;
while((int)ret.size()<472&&i<n){
vector<int> res = aask(i);
if(res[0]+res[1]>last[0]+last[1]) last=res;
i++;
}
ll rng = 0;
vector<ll> pj; forn(j,0,392) pj.push_back(j);
forn(k,0,392){
ll rj = rand()%(int(pj.size()));
int j = pj[rj];//pj[rj];
i=j*(512);
ll nmax = min(n,j*512+512);
if(i<=nmax-1){
ll rcalc = calc(i,nmax-1);
if(rcalc!=-1) return rcalc;
}
pj.erase(pj.begin()+rj);
//cout<<"tam "<<(int)pj.size()<<'\n';
}
cout<<"salio\n";
return 0;
}
