#include<bits/stdc++.h>
using namespace std;
using ll=int;
#include"prize.h"
const ll L=475/*1*/,N=2e5+2;
map<ll,ll>C;
map<array<ll,2>,array<ll,2>>mp;
ll x,lik,br,l,r,n,qu;
/*ll GG[N];
vector<int>ask(ll x){
ll le=0,ri=0;
for(int i=0;i<x;++i)if(GG[i]<GG[x])++le;
for(int i=x+1;i<n;++i)if(GG[i]<GG[x])++ri;
return{le,ri};
}*/
struct node{
ll lz=-1,s=0;
}st[4*N];
void push(int i,int l,int r){
if(st[i].lz!=-1){
int m=(l+r)/2;
st[2*i].s=st[i].lz*(m-l+1),st[2*i+1].s=st[i].lz*(r-m);
st[2*i].lz=st[2*i+1].lz=st[i].lz;
st[i].lz=-1;
}
}
void upd(int l,int r,int x,int i=1,int l2=0,int r2=n-1){
if(l<=l2&&r2<=r){
st[i].s=x*(r2-l2+1),st[i].lz=x;
return;
}
push(i,l2,r2);
int m2=(l2+r2)/2;
if(l<=m2)upd(l,r,x,2*i,l2,m2);
if(m2+1<=r)upd(l,r,x,2*i+1,m2+1,r2);
st[i].s=st[2*i].s+st[2*i+1].s;
}
int get(int l,int r,int i=1,int l2=0,int r2=n-1){
if(l<=l2&&r2<=r)return st[i].s;
push(i,l2,r2);
int m2=(l2+r2)/2,S=0;
if(l<=m2)S+=get(l,r,2*i,l2,m2);
if(m2+1<=r)S+=get(l,r,2*i+1,m2+1,r2);
return S;
}
mt19937_64 rng(time(0));
vector<int>askk(int aa){
//cout<<"A"<<endl;
ll G=get(aa,aa);
//cout<<G<<endl;
if(G){
G-=L;
if(mp.find({G-x})==mp.end()){
mp[{G,x-G}][0]=max(mp[{G,x-G}][0],aa);
mp[{G,x-G}][1]=max(mp[{G,x-G}][1],aa);
}
mp[{G,x-G}][0]=min(mp[{G,x-G}][0],aa);
mp[{G,x-G}][1]=max(mp[{G,x-G}][1],aa);
upd(mp[{G,x-G}][0],mp[{G,x-G}][1],G+L);
//cout<<"1: ";
//cout<<aa<<' '<<G<<' '<<x-G<<endl;
return{G,x-G};
}
vector<int>a=ask(aa);
++qu;
if(a[0]+a[1]!=x){
//cout<<"2: ";
//cout<<aa<<' '<<a[0]<<' '<<a[1]<<endl;
return a;
}
G=a[0];
if(mp.find({G-x})==mp.end()){
mp[{G,x-G}][0]=max(mp[{G,x-G}][0],aa);
mp[{G,x-G}][1]=max(mp[{G,x-G}][1],aa);
}
mp[{G,x-G}][0]=min(mp[{G,x-G}][0],aa);
mp[{G,x-G}][1]=max(mp[{G,x-G}][1],aa);
upd(mp[{G,x-G}][0],mp[{G,x-G}][1],G+L);
//cout<<"3: ";
//cout<<aa<<' '<<G<<' '<<x-G<<endl;
return{G,x-G};
}
int find_best(int NN){
n=NN;
for(int i=0;i<=4*NN;++i)
st[i]={-1,0};
mp.clear();
C.clear();
for(int i=0;i<L;++i){ //<L
vector<int>a=ask(i);
++C[a[0]+a[1]];
if(!a[0]&&!a[1])return i;
}
x=0,lik=L-1;
for(auto[u,v]:C)x=max(x,u);
br=L-C[x];
qu=0;
while(qu<L){
ll R=rng();
R=max(R,-R);
R%=n;
vector<int>a=askk(R);
if(!a[0]&&!a[1])return R;
}
while(lik<n){
l=lik+1,r=n-1;
while(l<=r){
ll m=(l+r)/2;
vector<int>a=askk(m);
if(!a[0]&&!a[1])return m;
else if(a[0]+a[1]==x){
if(a[0]!=br)r=m-1;
else l=m+1;
}else{
lik=m;
r=m-1;
}
}
++br;
//assert(0);
}
return -1;
}
/*signed main(){
ll NN;cin>>NN;
for(int i=0;i<NN;++i)
cin>>GG[i];
cout<<find_best(NN);
}*/
