#include "prize.h"
#include "bits/stdc++.h"
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
vvi Qu;
vi query(int i)
{
if (Qu[i][0] == -1)
Qu[i] = ask(i);
return Qu[i];
}
set<int> sums;
int reference;
vi interesting;
int cnt;
int r;
void resolve(int l)
{
if (r - l == 0)
return;
vi tmp = query(l);
if (tmp[0] + tmp[1] != reference)
{
resolve(l + 1);
interesting.push_back(l);
++cnt;
}
else
{
while (tmp[1] > cnt)
resolve((l + r) / 2);
}
r = l;
}
int find_best(int n)
{
Qu.assign(n, {-1, -1});
if (n <= 5000)
{ // query everything
for (int i = 0; i < n; i++)
{
std::vector<int> res = ask(i);
if (res[0] + res[1] == 0)
return i;
}
}
int j = 0;
while (n / (1 << (j + 1)) >= 500)
++j;
sums.clear();
int i;
for (i = 0; i < n; i += (1 << j))
{
vi tmp = query(i);
sums.insert(tmp[0] + tmp[1]);
}
reference = *sums.rbegin();
cnt = 0;
if (i >= n)
i -= (1 << j);
r = n;
while (i >= 0)
{
resolve(i);
i -= (1 << j);
}
for (int x : interesting)
{
vi tmp = query(x);
if (tmp[0] + tmp[1] == 0)
return x;
}
return 0;
}
