#include<bits/stdc++.h>
#include "prize.h"
using namespace std;
vector<pair<int,int>>ans;
unordered_map<int,set<int>>mp;
int calc(int st,int dr)
{
if (st>dr)
return -1;
int mij=(st+dr)/2;
vector<int>aux=ask(mij);
ans[mij]=make_pair(aux[0],aux[1]);
int sum=ans[mij].first+ans[mij].second;
if (sum==0)
return mij;
auto it=mp[sum].insert(mij).first;
if (it==mp[sum].begin() || ans[*prev(it)].first!=ans[mij].first){
int auxi=calc(st,mij-1);
if (auxi!=-1)
return auxi;
}
if (it==--mp[sum].end() || ans[*next(it)].second!=ans[mij].second){
int auxi=calc(mij+1,dr);
if (auxi!=-1)
return auxi;
}
return -1;
}
int find_best(int n)
{
ans.resize(n);
return calc(0,n-1);
}
