#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;
//grupos de tamanho 256;
int n,mx,best,mn;
vector<int> v[MAXN];
void pergunta(int x){
if(sz(v[x])) return;
v[x]=ask(x);
}
void dnc(int l,int r){
if(r<=l+1){
fall(i,l,r){
pergunta(i);
if(v[i][0]+v[i][1]<mn) mn=v[i][0]+v[i][1],best=i;
}
return;
}
while(l<=r){
pergunta(l);
if(v[l][0]+v[l][1]<mn) mn=v[l][0]+v[l][1],best=l;
if(v[l][0]+v[l][1]==mx) break;
l++;
}
if(l>r) return;
while(r>=l){
pergunta(r);
if(v[r][0]+v[r][1]<mn) mn=v[r][0]+v[r][1],best=r;
if(v[r][0]+v[r][1]==mx) break;
r--;
}
if(l>r) return;
int mei=(l+r)>>1;
while(mei<=r){
pergunta(mei);
if(v[mei][0]+v[mei][1]<mn) mn=v[mei][0]+v[mei][1],best=mei;
if(v[mei][0]+v[mei][1]==mx) break;
mei++;
}
if(mei<=r && v[r][0]>v[mei][0]) dnc(mei,r);
mei=(l+r)>>1;
while(mei>=l){
pergunta(mei);
if(v[mei][0]+v[mei][1]<mn) mn=v[mei][0]+v[mei][1],best=mei;
if(v[mei][0]+v[mei][1]==mx) break;
mei--;
}
if(mei>=l && v[mei][0]>v[l][0]) dnc(l,mei);
}
int find_best(int N){
n=N;
srand(time(0)); mn=inf;
fall(_,0,500){
int pos=rand()%n;
pergunta(pos);
mx=max(mx,v[pos][0]+v[pos][1]);
}
for(int ini=0;ini<n;ini+=256) dnc(ini,min(ini+255,n-1));
return best;
}
