#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define MP make_pair
#define P push
#define I insert
#define F first
#define S second
vector<pair<int,int> > v;
int sum[200000];
void query(int i){
vector<int> tv=ask(i);
v[i]={tv[0],tv[1]};
sum[i]=v[i].F+v[i].S;
return;
}
int find_best(int n) {
int lol=0;
for(int i=0;i<n;i++)v.PB(MP(-1,-1));
for(int i=0;i<500;i++){
query(i);
if(sum[i]==0)return i;
lol=max(lol,sum[i]);
}
for(int i=0;i<n;i++){
if(v[i].F==-1)query(i);
if(sum[i]==0)return i;
if(sum[i]!=lol)continue;
int l=i,r=n-1;
while(l<=r){
int m=(l+r)/2;
if(v[m].F==-1)query(m);
if(sum[m]==0)return m;
if(v[m]==v[i]){
l=m+1;
i=m;
}
else r=m-1;
}
}
return 0;
}
