#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
int l[200005],r[200005],answer=-1;
int sum[2000005],n;
void update(int id,int L,int R,int x){
if(L==R){
sum[id]=1;
return;
}
int m=(L+R)>>1;
if(x>=m) update(id*2,L,m,x);
else update(id*2+1,m+1,R,x);
sum[id]=sum[id*2]+sum[id*2+1];
}
int query(int id,int L,int R,int LL,int RR){
if(RR<L || R<LL) return 0;
if(LL<=L && R<=RR) return sum[id];
int m=(L+R)>>1;
return query(id*2,L,m,LL,RR)+query(id*2+1,m+1,R,LL,RR);
}
int find(int id,int L,int R,int x){
if(L==R) return L;
int m=(L+R)>>1;
if(x<=sum[id*2]) return find(id*2,L,m,x);
else return find(id*2+1,m+1,R,x-sum[id*2]);
}
void solve(int L,int R){
if(answer!=-1) return;
if(L+1>=R){
return;
}
int m=(L+R)>>1;
vector<int>res=ask(m);
l[m]=res[0];
r[m]=res[1];
if(l[m]+r[m]==0){
answer=m;
return;
}
update(1,0,n-1,m);
int y=query(1,0,n-1,0,m);
int x=find(1,0,n-1,y-1);
int z=find(1,0,n-1,y+1);
if(l[m]!=l[x] || r[m]!=r[x]){
solve(L,m);
}
if(answer!=-1) return;
if(l[m]!=l[z] || r[m]!=r[z]){
solve(m+1,R);
}
}
int find_best(int N){
// for(int i = 0; i < n; i++){
// std::vector<int> res = ask(i);
// if(res[0] + res[1] == 0)
// return i;
// }
n=N;
for(int i=0;i<n;i++){
l[i]=r[i]=-1;
}
int m=(n-1)/2;
vector<int>res=ask(0);
l[0]=res[0];
r[0]=res[1];
if(l[0]+r[0]==0) return 0;
update(1,0,n-1,0);
res=ask(n-1);
l[n-1]=res[0];
r[n-1]=res[1];
update(1,0,n-1,n-1);
if(l[n-1]+r[n-1]==0) return n-1;
solve(0,n-1);
return answer;
}
