#include "prize.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int ans = -1, cnt = 0, mx = 0;
vector<int> vec[500],wh;
map<int,int> rv;
vector<int> doask(int i, int k = 0){
vector<int> v;
if(rv.count(i) && !k) v = vec[rv[i]];
else v = ask(i);
if(v[0] == 0 && v[1] == 0) ans = i;
return v;
}
void solve(int l, int r, int x){
if(ans != -1) return;
int m1 = (l + r) >> 1, t = 0, m2 = m1 + 1, f;
vector<int> v;
while(m1 >= l || m2 < r){
if(m1 >= l){
v = doask(m1);
m1--;
if(v[0] + v[1] == mx){
f = 0;
break;
}
t++;
}
if(m2 < r){
v = doask(m2);
m2++;
if(v[0] + v[1] == mx){
f = 1;
break;
}
t++;
}
}
if(!f){
if(l <= m1 && v[0] > cnt) solve(l, m1 + 1, v[1]);
cnt += t;
if(m2 < r && v[1] - x - t > 0) solve(m2, r, x);
}else{
if(l <= m1 && v[0] > cnt + t) solve(l, m1 + 1, v[1] + t);
cnt += t;
if(m2 < r && v[1] - x > 0) solve(m2, r, x);
}
}
int find_best(int n) {
queue<pair<int,int>> q;
q.push({0,n});
while((int)wh.size()<=min(n,500)){
int l=q.front().first,r=q.front().second,m=(l+r)>>1;
q.pop();
if(!rv.count(m)){
rv[m]=wh.size();
wh.pb(m);
}
if(r-l>1){
q.push({l,m});
q.push({m,r});
}
}
for(int i = 0; i < min(n, 500); i++){
vec[i] = doask(wh[i], 1);
if(vec[i][0] + vec[i][1] > mx) mx = vec[i][0] + vec[i][1];
}
int x = 0;
while(n){
vector<int> v = doask(n - 1);
n--;
if(v[0] + v[1] == mx) break;
x++;
}
solve(0, n, x);
return ans;
}
