#include "bits/stdc++.h"
using namespace std;
#include "prize.h"
#ifdef LOCAL
#include "debug.cpp"
#else
#define debug(...)
#define debugArr(...)
#endif
pair<int,int> ret[200001];
int fin = -1;
pair<int,int> ans(int x){
if(ret[x].first!=-1)return ret[x];
vector<int>lol = ask(x);
ret[x] = {lol[0],lol[1]};
if(ret[x].first==ret[x].second&&ret[x].first==0){
fin = x;
}
return ret[x];
}
void solve(int l,int r){
if(fin!=-1)return ;
if(l>r)return ;
if(l==r){
ans(l);
return ;
}
while(ans(l).first+ans(l).second!=ans(r).first+ans(r).second){
while(ans(l).first+ans(l).second<ans(r).first+ans(r).second)l++;
while(ans(l).first+ans(l).second>ans(r).first+ans(r).second)r--;
}
int mid = (l+r)/2;
if(ans(l).second==ans(r).second){
return ;
}
solve(l,mid);
solve(mid,r);
}
int find_best(int n){
for(int i = 0;i<n;i++){
ret[i] = {-1,-1};
}
solve(0,n-1);
return fin;
}
