#include "prize.h"
#include<vector>
#include<set>
using namespace std;
const int maxn=2e5+10;
const int koren=450;
int res=-1;
int maxi=0;
set<pair<int,int> > veliki;
int fwt[maxn];
int n;
void dodaj(int x){
x++;
for(;x<maxn;x+=x&-x) fwt[x]++;
}
int qry(int x){
int ret=0;
x++;
if(x==0) return 0;
for(;x>0;x-=x&-x) ret+=fwt[x];
return ret;
}
bool uradi(int l,int r,bool levi,bool desni){
if(l>r) return false;
int mid=l+(r-l)/2;
vector<int> rez=ask(mid);
int klkl=rez[0],klkr=rez[1];
if(klkl+klkr<maxi){
dodaj(mid);
veliki.emplace(pair<int,int>(mid,klkl+klkr));
}
if(klkl+klkr==0){
res=mid;
return true;
}
if(levi){
if(klkl+klkr==maxi){
klkl-=qry(l-1);
}
if(klkl>0) if(uradi(l,mid-1,true,false)) return true;
}
if(desni){
if(klkl+klkr==maxi){
klkr-=qry(n-1)-qry(r);
}
if(klkr>0) uradi(mid+1,r,false,true);
}
if(!levi && klkl>0) if(uradi(l,mid-1,false,desni)) return true;
if(!desni && klkr>0) if(uradi(mid+1,r,levi,false)) return true;
return false;
}
int find_best(int _n) {
n=_n;
for(int i=0;i<koren;i++){
auto rez=ask(i);
maxi=max(maxi,rez[0]+rez[1]);
if(rez[0]+rez[1]==0) return i;
}
uradi(koren,n-1,true,true);
return res;
}
