#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);
}
void solve(int l,int r,int lcnt,int rcnt){
// cout << l << " " << r << " " << lcnt << " " << rcnt << endl;
if(l > r) return;
if(lcnt+rcnt == mx) return;
int mid = (l+r)/2;
int m = mid;
int bizz = 0;
while(mid >= l){
vi gg = asky(mid);
if(gg[0]+gg[1] == mx){
solve(l,mid-1,lcnt,gg[1]);
solve(m+1,r,gg[0]+bizz,rcnt);
return;
}
possible.pb({gg[0]+gg[1],mid});
bizz++;
mid--;
}
solve(m+1,r,lcnt+bizz,rcnt);
}
int find_best(int n) {
for(int i = 0; i < 300; i++){
int ind = RNG()%n;
// cout << ind << endl;
vi gg = asky(ind);
mx = max(mx,gg[0]+gg[1]);
}
solve(0,n-1,0,0);
sort(all(possible));
return possible[0].S;
}
