#include "prize.h"
#include <vector>
using namespace std;
using vi = vector<int>;
using pii = pair<int, int>;
const int mx = 200'000;
int n;
vi ans[mx], prize(mx, 0);
int prizecount;
void solve(int l, int r)
{
if(r < l) return;
int m = (l+r)/2;
int leftcount = ans[l-1][0];
int mm = -1;
for(int k = m; k >= l; k--)
{
if(ans[k].empty())
ans[k] = ask(k);
if(ans[k][0] + ans[k][1] == prizecount)
{
mm = k;
break;
}
else
{
prize[k] = 1;
}
}
if(mm != -1)
{
int rightcount = ans[mm][0];
if(rightcount - leftcount >= 1)
{
solve(l, mm-1);
}
}
int mm2 = -1;
for(int k2 = m; k2 <= r; k2++)
{
if(ans[k2].empty())
ans[k2] = ask(k2);
if(ans[k2][0] + ans[k2][1] == prizecount)
{
mm2 = k2;
break;
}
else
{
prize[k2] = 1;
}
}
if(mm2 != -1)
solve(mm2+1, r);
}
const int mxq = 200'000;
const int threshold = 1000;
int find_best(int n_)
{
n = n_;
if(n <= mxq)
{
pii mn{5*n, -1};
for(int i = 0; i < n; i++)
{
vi z = ask(i);
mn = min(mn, {z[0] + z[1], i});
}
return mn.second;
}
int maxscore = -1;
int ind = 0;
for(int i = 0; i < threshold; i++)
{
ans[i] = ask(i);
if(ans[i][0] + ans[i][1] > maxscore)
{
maxscore = ans[i][0] + ans[i][1];
ind = i;
}
}
for(int i = 0; i < ind; i++)
prize[i] = 1;
prizecount = maxscore;
solve(ind+1, n-1);
for(int i = 0; i < n; i++)
if(prize[i])
if(ans[i][0] + ans[i][1] == 0)
return i;
return -1;
}
