#include "prize.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;
int bad = 0;
vector<int> res[200005];
pii how(int k)
{
if (res[k].size() == 0)
res[k] = ask(k);
return pii(res[k][0], res[k][1]);
}
int find_best(int n)
{
vector<int> remain;
vector<int> v;
for (int i = 0; i < n; i++)
remain.emplace_back(i);
for (int i = 0; i < min(n, 501); i++)
bad = max(bad, how(i).F + how(i).S);
for (int t = 0; t <= 500; t++)
{
int l = 0, r = remain.size(), mid;
while (r - l > 1)
{
mid = (l + r) / 2;
if (how(mid).F + how(mid).S < bad)
{
l = mid;
goto oyes;
}
else if (how(mid).F > 0)
r = mid;
else
l = mid;
}
oyes:
if (how(l).F + how(l).S < bad)
v.emplace_back(l);
else
break;
}
for (int i : v)
if(how(i) == pii(0, 0))
return i;
return 0;
}
