//chockolateman
#include<bits/stdc++.h>
#include "prize.h"
using namespace std;
int least_expensive = 0;
pair<int,int> memo[200005];
pair<int,int> my_ask(int i)
{
if(memo[i].first == -1)
{
vector<int> temp = ask(i);
memo[i] = {temp[0],temp[1]};
}
return memo[i];
}
int search(int start,int end,int prv = 0,int nxt = 0)
{
if(start > end)
return -1;
int mid = (start + end)/2;
int l = -1,r = -1;
pair<int,int> cur = my_ask(mid);
if(cur.first + cur.second == 0)
return mid;
while(mid > start && cur.first + cur.second != least_expensive)
{
if(cur.first + cur.second == 0)
return mid;
mid--;
cur = my_ask(mid);
}
if(cur.first > prv)
l = search(start,mid-1,prv,cur.second);
mid = (start + end)/2;
cur = my_ask(mid);
while(mid < end && cur.first + cur.second != least_expensive)
{
if(cur.first + cur.second == 0)
return mid;
mid++;
cur = my_ask(mid);
}
if(cur.second > nxt)
r = search(mid+1,end,cur.first,nxt);
return max(l,r);
}
int find_best(int n)
{
for(int i = 0 ; i < n ; i++)
memo[i] = {-1,-1};
pair<int,int> temp;
int pos;
for(int i = 0 ; i < min(500,n) ; i++)
{
temp = my_ask(i);
least_expensive = max(least_expensive,temp.first + temp.second);
if(temp.first + temp.second == least_expensive)
pos = i;
}
return search(0,n-1);
}
