#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>> asked;
int cate;
pair<int,int> query(int x)
{
if(asked[x].first==-1)
{
vector<int> cv = ask(x);
asked[x] = {cv[0],cv[1]};
cate = max(cate, cv[0] + cv[1]);
}
return asked[x];
}
mt19937 rnd(time(0));
int find_best(int n)
{
asked.resize(n,{-1,-1});
/*for(int pas=0;pas<1000;pas++)
{
int x = rnd()%n;
query(x);
}*/
int ult=-1,pref=0,capdr=n-1;
query(0);
set<int> bune;
while(1)
{
/*auto it = bune.upper_bound(ult);
if(it != bune.end())
{
int x = (*it) - 1;
if(query(x).first + query(x).second == cate && query(x).first == pref)
{
pref++;
ult = x+1;
continue;
}
}*/
int st=ult+1,dr=capdr,ans=-1;
//query(st);
while(st<=dr)
{
int mij=(st+dr)/2;
if(query(mij).first==0)
{
if(query(mij).first + query(mij).second == 0)
return mij;
st = mij+1;
}
else if(query(mij).first + query(mij).second < cate || query(mij).first > pref)
{
ans = mij;
dr = mij-1;
}
else
st = mij+1;
}
if(ans==-1)
break;
if(query(ans).first + query(ans).second == 0)
return ans;
pref++;
ult = ans;
}
assert(0);
return 0;
}
