#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> kaes[200005];
ll su,ma=0,x;
int rek(ll l,ll r,ll a,ll b){
ll k=(l+r)/2,x,arv;
bool en=0,par=0;
if(kaes[k][0]==-1) kaes[k]=ask(k);
if(kaes[k][0]+kaes[k][1]==0) return k;
x=k;
while(kaes[x][0]+kaes[x][1]<su){
x++;
if(x==r+1) break;
if(kaes[x][0]==-1) kaes[x]=ask(x);
if(kaes[x][0]+kaes[x][1]==0) return x;
if(kaes[x][0]==a) en=1;
if(kaes[x][0]==b) par=1;
}
if(x==r){
x=k;
while(kaes[x][0]+kaes[x][1]<su){
x--;
if(x==l-1) break;
if(kaes[x][0]==-1) kaes[x]=ask(x);
if(kaes[x][0]+kaes[x][1]==0) return x;
if(kaes[x][0]==a) en=1;
if(kaes[x][0]==b) par=1;
}
}
if(!en){
if(x<=k) arv=rek(l,x-1,a,kaes[x][0]);
else arv=rek(l,k-1,a,kaes[x][0]-(x-k));
if(arv!=-1) return arv;
}
if(!par){
if(x>=k) arv=rek(x+1,r,kaes[x][0],b);
else arv=rek(k+1,r,kaes[x][0]-(k-x),b);
if(arv!=-1) return arv;
}
return -1;
}
int find_best(int n) {
ll l=0, r=n-1;
vector<int> res;
for(int i=0; i<10; i++){
x=rand()%n;
res=ask(x);
su=res[0]+res[1];
kaes[x]=res;
ma=max(ma,su);
if(su==0) return x;
}
for(int i=0; i<n; i++) kaes[i].resize(2),kaes[i][0]=-1;
return rek(l,r,0,su);
}
