#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
const int maxk = 475;
map<int, vector<int> > me; // tam si pamatame nase doterajsie queries
bool di = false;
int notl;
vector<int> ask2(int x)
{
if (!me.count(x)) return me[x] = ask(x);
else return me[x];
}
bool lolipop(int x)
{
vector<int> v = ask2(x);
return v[0] + v[1] == notl;
}
void rek(int l, int r, int cntl, int cntr)
{
if (r < l || cntl + cntr == notl) return;
int mr = (l + r) / 2, ml = mr;
while (ml >= l && !lolipop(ml)) ml--;
while (mr <= r && !lolipop(mr)) mr++;
if (ml > l)
{
vector<int> vl = ask2(ml);
rek(l, ml-1, cntl, vl[1]);
}
if (mr < r)
{
vector<int> vr = ask2(mr);
rek(mr+1, r, vr[0], cntr);
}
}
int find_best(int n)
{
for (int i = 0; i < min(n, maxk); i++) ask2(i);
for (const pair<int, vector<int> > &i : me)
notl = max(notl, i.second[0] + i.second[1]);
rek(0, n-1, 0, 0);
for (const pair<int, vector<int> > &i : me) if (i.second[0] + i.second[1] == 0) return i.first;
assert(false);
}
