#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> possible;
int rangMax;
pair<int,int> ans[200005];
pair<int,int> query(int x)
{
if(ans[x] != make_pair(-1, -1)) return ans[x];
auto res = ask(x);
ans[x] = {res[0], res[1]};
return ans[x];
}
int rang(int x)
{
return query(x).first + query(x).second;
}
void divide(int st, int dr, int outleft, int outright)
{
int mid = (st + dr) / 2, pos = mid;
while(pos <= dr && rang(pos) != rangMax)
{
possible.push_back(pos);
++pos;
}
if(pos <= dr)
{
if(query(pos).second > outright)
divide(pos+1, dr, query(pos).first, outright);
if(query(pos).first > outleft + (pos - mid))
divide(st, mid-1, outleft, query(pos).second + (pos - mid));
return;
}
pos = mid;
while(pos >= st && rang(pos) != rangMax)
{
possible.push_back(pos);
pos--;
}
if(pos >= st)
{
if(query(pos).first > outleft)
divide(st, pos-1, outleft, query(pos).second);
if(query(pos).second > outright + (mid - pos))
divide(mid+1, dr, query(pos).first + (mid - pos), outright);
return;
}
}
int find_best(int n)
{
int i;
for(i=0; i<n; ++i) ans[i] = {-1, -1};
for(i=0; i<500 && i<n; ++i)
rangMax = max(rangMax, rang(i));
divide(0, n-1, 0, 0);
for(auto it : possible)
if(rang(it) == 0) return it;
assert(0);
}
