#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<#x<<", "<<#y<<" = "<<x<<", "<<y<<"\n";}
#define pb push_back
#define all(x) x.begin(), x.end()
const int inf=1000000100;
const int MAXN=200010;
int n, m, k, shit, ans=-1;
pii A[MAXN];
pii Ask(int i){
if (A[i].first!=-1) return A[i];
auto v=ask(i);
A[i]={v[0], v[1]};
return A[i];
}
int ord(int i){
return Ask(i).first+Ask(i).second;
}
void divide(int tl, int tr, int ted){
if (!ted || tr-tl<1 || ans!=-1) return ;
// cerr<<"divide "<<tl<<" "<<tr<<" "<<ted<<"\n";
int mid=(tl+tr)>>1;
int l=mid, r=mid, turn=0;
while (ted){
int i;
turn^=1;
if (turn) i=r++;
else i=--l;
if (!ord(i)){
ans=i;
return ;
}
if (ord(i)!=shit){
ted--;
continue ;
}
int tedl=Ask(i).first-Ask(tl-1).first-(r-l-1);
divide(tl, l, tedl);
divide(r, tr, ted-tedl);
return ;
}
divide(r, tr, ted);
}
int find_best(int _n){
memset(A, -1, sizeof(A));
n=_n;/*
if (n<5000){
for (int i=0; i<n; i++)
if (!ord(i)) return i;
assert(0);
}*/
// shit=1;
int T=480;
for (int i=0; i<T; i++){
if (!ord(i)) return i;
shit=max(shit, ord(i));
}
for (int i=T; i<n; i++){
if (!ord(i)) return i;
if (ord(i)==shit){
divide(i+1, n, Ask(i).second);
return ans;
}
}
assert(0);
}
