#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define pb push_back
#define F first
#define S second
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());
vector<pii> possible;
int mx;
vi done[200005];
vi asky(int ind){
// cout << ind << endl;
if(done[ind].size()) return done[ind];
return done[ind] = ask(ind);
}
int solve(int l,int r,int lcnt,int rcnt){
// cout << l << " " << r << " " << lcnt << " " << rcnt << endl;
if(l > r) return -1;
if(lcnt+rcnt == mx) return -1;
int mid = l+(RNG()%(r-l+1));
int m = mid;
int bizz = 0;
while(mid >= l){
vi gg = asky(mid);
if(gg[0]+gg[1] == mx){
if(RNG()%2){
int pos = solve(l,mid-1,lcnt,gg[1]);
if(pos != -1) return pos;
return solve(m+1,r,gg[0]+bizz,rcnt);
}
else{
int pos = solve(m+1,r,gg[0]+bizz,rcnt);
if(pos != -1) return pos;
return solve(l,mid-1,lcnt,gg[1]);
}
}
if(gg[0]+gg[1] == 0) return mid;
possible.pb({gg[0]+gg[1],mid});
bizz++;
mid--;
}
return solve(m+1,r,lcnt+bizz,rcnt);
}
int find_best(int n){
for(int i = 0; i < 500; i++){
int ind = RNG()%n;
vi gg = asky(ind);
mx = max(mx,gg[0]+gg[1]);
}
return solve(0,n-1,0,0);
}
