#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
const int koren=480;
int res=-1;
int maxi=0;
int n;
int q=0;
map<int,int> najr;
map<int,int> najl;
int find_best(int _n) {
n=_n;
map<int,int> kurac;
vector<int> sta(koren);
for(int i=0;i<koren;i++){
auto rez=ask(i);
q++;
maxi=max(maxi,rez[0]+rez[1]);
kurac[rez[0]+rez[1]]++;
sta[i]=rez[0]+rez[1];
if(rez[0]+rez[1]==0) return i;
}
int klk=koren-kurac[maxi];
int tren=koren-1;
while(true){
int l=tren+1;
int r=n-1;
int sled=-1;
if(najr.find(klk)!=najr.end()) l=najr[klk]+1;
auto it=najl.upper_bound(klk);
if(it!=najl.end()) r=it->second-1;
while(l<=r){
int mid=l+(r-l)/2;
auto rez=ask(mid);
q++;
if(q==10000) exit(-1);
if(rez[0]+rez[1]==0) return mid;
if(rez[0]+rez[1]<maxi){
sled=mid;
r=mid-1;
}else{
najr[rez[0]]=max(najr[rez[0]],mid);
if(najl.find(rez[0])==najl.end()) najl[rez[0]]=n;
najl[rez[0]]=min(najl[rez[0]],mid);
if(rez[0]==klk){
l=mid+1;
}else{
r=mid-1;
}
}
}
tren=sled;
klk++;
}
return res;
}
