#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
int const NMAX=200005;
vector<int>rasp[NMAX];
int maxim;
#define pii pair<int,int>
#define ff first
#define ss second
int raspuns_final;
void intrb(int i){
vector<int>v=ask(i-1);
rasp[i]=v;
if(v[0]+v[1]==0)
raspuns_final=i-1;
}
pii extinde(int pos){
if(rasp[pos][0]+rasp[pos][1]==maxim)
return {pos,pos};
int l=pos;
while(rasp[l-1].empty()){
--l;
intrb(l);
if(rasp[l][0]+rasp[l][1]==maxim)
break;
}
int r=pos;
while(rasp[r+1].empty()){
++r;
intrb(r);
if(rasp[r][0]+rasp[r][1]==maxim)
break;
}
return {l,r};
}
void cauta(int l,int r){
int mij=(l+r)/2;
intrb(mij);
pii per=extinde(mij);
if(l<per.ff && rasp[l-1]!=rasp[per.ff])
cauta(l,per.ff-1);
if(per.ss<r && rasp[per.ss]!=rasp[r+1])
cauta(per.ss+1,r);
}
int find_best(int n){
int pas=sqrt(n);
int i;
for(i=pas;i<=n;i+=pas){
intrb(i);
maxim=max(maxim,rasp[i][0]+rasp[i][1]);
}
rasp[0]={0,maxim};
rasp[n+1]={maxim,0};
for(i=pas;i<=n;i+=pas)
extinde(i);
int ult=0;
for(i=1;i<=n+1;++i)
if(!rasp[i].empty() && rasp[i][0]+rasp[i][1]==maxim){
if(rasp[ult+1].empty())
cauta(ult+1,i-1);
ult=i;
}
return raspuns_final;
}
