#include "prize.h"
#include <vector>
using namespace std;
int nonlollipop = 0;
int diamond_search(int a, int b, int L, int R) //extra non-lollipops on left and right
{
if(b < a) return -1;
else if(nonlollipop - L - R == (b-a+1)) //a..b is completely filled with prizes
{
for(int i = a; i <= b; i++)
{
vector<int> A = ask(i);
if(A[0] + A[1] == 0) return i;
}
return -1;
}
vector<int> A;
int m;
for(m = (a+b)/2; m <= b; m++)
{
A = ask(m);
if(A[0] + A[1] == 0) return m;
else if(A[0] + A[1] == nonlollipop) //m is a lollipop
{
return max( diamond_search(a, (a+b)/2-1, L, A[1]), diamond_search(m+1, b, A[0], R) );
}
}
return diamond_search(a, (a+b)/2-1, L, R + (b - (a+b)/2 + 1));
}
int find_best(int n)
{
for(int i = 1; i <= min(500, n); i++)
{
vector<int> A = ask(i);
nonlollipop = max(nonlollipop, A[0]+A[1]);
}
return diamond_search(0, n-1, 0, 0);
}
