#include "prize.h"
#include <vector>
#include <iostream>
using namespace std;
using vi = vector<int>;
using pii = pair<int, int>;
const int mx = 200'000;
int qrc = 0;
int n;
vi ans[mx], prize(mx, 0);
int prizecount;
void compute(int i)
{
if(ans[i].empty())
{
qrc++;
if(qrc == 10'000) while(1);
ans[i] = ask(i);
}
}
void solve(int l, int r)
{
if(r < l) return;
// cerr << "solve " << l << ' ' << r << '\n';
int m = (l+r)/2;
int lm = -1, rm = -1;
for(int i = m; i >= l; i--)
{
compute(i);
if(ans[i][0] + ans[i][1] == prizecount)
{
lm = i;
break;
}
}
for(int i = m; i <= r; i++)
{
compute(i);
if(ans[i][0] + ans[i][1] == prizecount)
{
rm = i;
break;
}
}
// cerr << m << ' ' << lm << ' ' << rm << '\n';
if(lm >= 0)
if(ans[lm][0] - ans[l-1][0] >= 1)
solve(l, lm-1);
if(rm >= 0)
if(ans[r+1][0] - ans[rm][0] >= 1)
solve(rm+1, r);
if(lm == -1)
lm = l-1;
if(rm == -1)
rm = r+1;
for(int i = lm+1; i < rm; i++)
prize[i] = 1;
}
const int threshold = 450; //a lollipop will be found in the first (threshold) elements.
int find_best(int n_)
{
// cerr << "called\n";
n = n_;
int maxscore = -1;
int ind = 0;
for(int i = 0; i < min(threshold, n); i++)
{
compute(i);
if(ans[i][0] + ans[i][1] > maxscore)
{
maxscore = ans[i][0] + ans[i][1];
ind = i;
}
}
// cerr << "A\n";
// cerr << "ind = " << ind << '\n';
for(int i = 0; i < ind; i++)
prize[i] = 1;
prizecount = maxscore;
int ind2 = 0;
// cerr << "B\n";
for(int i = n-1; 1; i--)
{
compute(i);
if(ans[i][0] + ans[i][1] == prizecount)
{
ind2 = i;
break;
}
}
// cerr << "ind2 = " << ind2 << '\n';
// cerr << "C\n";
for(int i = ind2+1; i < n; i++)
prize[i] = 1;
solve(ind+1, ind2-1);
// cerr << "D\n";
// for(int i = 0; i < n; i++) cerr << prize[i] << ' ';
// cerr << '\n';
for(int i = 0; i < n; i++)
if(prize[i])
if(ans[i][0] + ans[i][1] == 0)
return i;
return -1;
}
