#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);
}
void expand(ll l, ll r){
ll mid =(l+r)/2;
if((int)ret.size()>472) return;
if(l==r-1) return;
if(aask(l)[0]==aask(r)[0] && aask(l)[1]==aask(r)[1]) return;
expand(l,mid);
expand(mid,r);
}
int find_best(int n) {
srand(time(NULL));
ll i = 0;
vector<int> ares = {-1,-1};
vector<int> last = {-1,-1};
expand(0,n-1);
return calc(0,n-1);
return 0;
}
