#include <bits/stdc++.h>
using namespace std;
#include "prize.h"
struct seg
{
int n;
vector<int> tr;
seg(int N): n(N)
{
tr.resize(n*2);
}
int qr(int a, int b)
{
a += n; b += b+1;
int ans = 0;
while (a < b)
{
if (a&1) ans += tr[a++];
if (b&1) ans += tr[--b];
a /= 2; b /= 2;
}
return ans;
}
void upd(int k)
{
k += n;
do tr[k]++;
while (k /= 2);
}
};
vector<vector<int>> dp;
vector<int> sk(int i)
{
if (dp[i][0] == -1) dp[i] = ask(i);
return dp[i];
}
int ntlar = 0;
int N;
void findlar()
{
srand(clock());
for (int i = 0; i < 3; i++)
{
auto t = sk(((rand()%N)+N)%N);
ntlar = max(ntlar, t[0] + t[1]);
}
}
bool islar(int i)
{
auto t = sk(i);
return ntlar == t[0] + t[1];
}
seg tr(1);
int find(int l, int r, int cnt)
{
if (r < l) return -1;
int x = 0;
int m = (l + r) / 2;
int lm = (l + r) / 2;
while (!islar(lm) && lm >= l)
{
auto t = sk(lm);
if (t[0] + t[1] == 0) return lm;
tr.upd(lm);
lm--;
x++;
}
if (lm <= l) if (cnt == x) return -1;
else return find(m+1, r, cnt - x);
auto t = sk(lm);
int tm = t[0] - tr.qr(0, l-1);
int ans = -1;
if (tm > 0) ans = find(l, lm-1, tm);
if (ans != -1) return ans;
if (tm + x < cnt) return find(m+1, r, cnt - x - tm);
return -1;
}
int spec(int n)
{
for (int i = 0; i < n; i++)
{
auto t = ask(i);
if (t[0] + t[1] == 0) return i;
}
return -1;
}
int find_best(int n)
{
if (n < 5000) return spec(n);
dp.resize(n, {-1, -1});
tr = seg(n);
N = n;
findlar();
return find(0, n-1, ntlar);
}
