#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;
namespace
{
int n, bad = 0;
vector<int> res[200005];
int bit[200005];
};
void modify(int pos)
{
pos++;
for (int i = pos; i <= n; i += (i & -i))
bit[i]++;
}
int query(int pos)
{
int ans = 0;
pos++;
for (int i = pos; i ; i -= (i & -i))
ans += bit[i];
return ans;
}
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)
{
::n = 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, 601); i++)
bad = max(bad, how(i).F + how(i).S);
for (int t = 0; t <= 600; 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 > query(mid))
r = mid;
else
l = mid;
}
oyes:
if (how(l).F + how(l).S < bad)
{
v.emplace_back(l);
vector<int> nxt;
for (int i : remain)
if (i != l)
nxt.emplace_back(i);
modify(l);
remain = nxt;
}
else
break;
}
for (int i : v)
if (how(i) == pii(0, 0))
return i;
return 0;
}
