#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rng(i,l,r) for(int i=(l); i<(r); i++)
#define all(x) x.begin(),x.end()
using ll=long long;
const int INF=INT_MAX>>1;
vector<vector<int>> answers(200010,{-1,-1});
int ret=-1;
vector<int> query(int n){
if(answers[n][0]!=-1)return answers[n];
vector<int> now=ask(n);
if(now[0]+now[1]==0)ret=n;
answers[n]=now;
return now;
}
int find_best(int n) {
int MAX_OTHERS=min(n-1,500);
int candy=0;
rep(i,MAX_OTHERS+1){
vector<int> now=query(i);
candy=max(candy,now[0]+now[1]);
}
int pos=MAX_OTHERS+1;
while(pos<n){
vector<int> now=query(pos);
if(now[0]+now[1]!=candy){
pos++;
continue;
}
int ok=pos,ng=n;
while(ng-ok>1){
int mid=(ok+ng)>>1;
vector<int> mnow=query(mid);
if(mnow[0]+mnow[1]==candy&&mnow[0]==now[0]){
ok=mid;
}
else{
ng=mid;
}
}
pos=ok+1;
}
return ret;
}
