#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
int rangMax;
pair<int,int> ans[200005];
int found = -1;
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)
{
if(found != -1) return;
int mid = (st + dr) / 2, pos = mid;
while(found == -1 && pos <= dr && rang(pos) != rangMax)
{
if(rang(pos) == 0) found = pos;
++pos;
}
if(found != -1) return;
if(pos <= dr)
{
if(query(pos).second > outright)
divide(pos+1, dr, query(pos).first, outright);
if(found != -1) return;
if(query(pos).first > outleft + (pos - mid))
divide(st, mid-1, outleft, query(pos).second + (pos - mid));
return;
}
if(found != -1) return;
pos = mid;
while(found == -1 && pos >= st && rang(pos) != rangMax)
{
if(rang(pos) == 0) found = pos;
pos--;
}
if(found != -1) return;
if(pos >= st)
{
if(query(pos).first > outleft)
divide(st, pos-1, outleft, query(pos).second);
if(found != -1) return;
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};
mt19937 mt(time(0));
for(i=0; i<200; ++i)
rangMax = max(rangMax, rang( uniform_int_distribution<int> (0, n-1) (mt) ));
divide(0, n-1, 0, 0);
assert(found != -1);
return found;
}
