#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 200005;
vector<int> vv[N];
vector<int> qry(int x)
{
if (!vv[x].empty())
return vv[x];
return vv[x] = ask(x);
}
int s;
int ans;
bool rec(int l, int r, int ql, int qr)
{
if (l > r)
return false;
int m = (l + r) / 2;
while (m <= r)
{
if (qry(m)[0] + qry(m)[1] == s)
{
if (qry(m)[0] - ql > 0)
if (rec(l, m - 1, ql, qry(m)[1]))
return true;
if (qry(m)[1] - qr > 0)
if (rec(m + 1, r, qry(m)[0], qr))
return true;
return false;
}
else
{
if (qry(m)[0] + qry(m)[1] == 0)
{
ans = m;
return true;
}
++m;
}
}
--m;
while (m >= l)
{
if (qry(m)[0] + qry(m)[1] == s)
{
if (qry(m)[0] - ql > 0)
if (rec(l, m - 1, ql, qry(m)[1]))
return true;
if (qry(m)[1] - qr > 0)
if (rec(m + 1, r, qry(m)[0], qr))
return true;
return false;
}
else
{
if (qry(m)[0] + qry(m)[1] == 0)
{
ans = m;
return true;
}
--m;
}
}
++m;
return false;
}
int find_best(int n)
{
for (int x = 0; x < min(n, 700); ++x)
{
s = max(s, qry(x)[0] + qry(x)[1]);
if (s > 100)
break;
}
assert(rec(0, n - 1, 0, 0));
return ans;
}
