#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
#define fall(i,a,b) for(int i=a;i<=b;i++)
#define rfall(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
const int inf=1e7;
const int MAXN=2e5+10;
vector<int> memo[MAXN];
int find_best(int n){
srand(time(0));
int mx=0,q=0;
fall(_,0,500){
int pos=rand()%n;
auto v=memo[pos]; if(!sz(memo[pos])) v=ask(pos),q++; memo[pos]=v;
mx=max(mx,v[0]+v[1]);
}
int ini=0,fim=0,best=0,mn=inf;
while(ini<=fim){
int pos=(ini+fim)>>1;
auto v=memo[pos]; if(!sz(memo[pos])) v=ask(pos),q++; memo[pos]=v;
if(v[0]+v[1]==0) return pos;
if(v[0]+v[1]<mn) best=pos,mn=v[0]+v[1];
if(v[0]) fim=pos-1;
else ini=pos+1;
}
int pos=best+1;
while(pos<n){
if(mn==0) return best;
int curval=0;
while(pos<n){
auto v=memo[pos]; if(!sz(memo[pos])) v=ask(pos),q++; memo[pos]=v;
if(v[0]+v[1]<mn) mn=v[0]+v[1],best=pos;
curval=v[0];
if(v[0]+v[1]==mx) break;
pos++;
if(mn==0) return best;
}
if(pos==n-1) break;
rfall(i,17,0){
if(mn==0) return best;
if(pos+(1<<i)>=n) continue;
int np=pos+(1<<i);
while(np>pos){
if(mn==0) return best;
auto v=memo[np]; if(!sz(memo[np])) v=ask(np),q++; memo[np]=v;
if(v[0]+v[1]<mn) mn=v[0]+v[1],best=np;
if(v[0]+v[1]==mx) break;
np--;
}
if(np==pos || curval==memo[np][0]){
pos+=(1<<i);
while(pos<n){
if(mn==0) return best;
auto v=memo[pos]; if(!sz(memo[pos])) v=ask(pos),q++; memo[pos]=v;
if(v[0]+v[1]<mn) mn=v[0]+v[1],best=pos;
curval=v[0];
if(v[0]+v[1]==mx) break;
pos++;
}
}
}
}
return best;
}
