#include<bits/stdc++.h>
#include "prize.h"
#define MAXN 200007
using namespace std;
int nn,r,res;
bool used[MAXN];
vector<int> w;
int solve(int l,int r,int reml,int remr){
if(l>r)return 0;
int mid=(l+r)/2,p;
vector<int> curr;
while(mid<=r){
curr=ask(mid);
if(curr[0]+curr[1]==res)break;
if(curr[0]+curr[1]==0)return mid;
mid++;
}
if(mid==r+1){
mid=(l+r)/2-1;
while(mid>=l){
curr=ask(mid);
if(curr[0]+curr[1]==res)break;
if(curr[0]+curr[1]==0)return mid;
mid--;
}
if(mid==l-1)return 0;
curr[0]-=reml;
if(curr[0]>0){
return solve(l,mid-1,reml,remr+(r-mid));
}
return 0;
}else{
curr[0]-=reml-(mid-(l+r)/2);
curr[1]-=remr;
if(curr[0]>0){
p=solve(l,(l+r)/2-1,reml,remr+curr[1]+(mid-(l+r)/2));
if(p!=0)return p;
}
if(curr[1]>0){
p=solve(mid+1,r,reml+curr[0],remr);
if(p!=0)return p;
}
return 0;
}
return 0;
}
int find_best(int N){
nn=N;
for(int i=1;i<=40;i++){
r=rand()%nn; w=ask(r);
res=max(res,w[0]+w[1]);
}
return solve(0,nn-1,0,0);
}
