#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
struct SegTree {
int n;
vi v;
void update(int i, int val)
{
int p = i + n;
v[p] = val;
while (p /= 2)
v[p] = v[2 * p] + v[2 * p + 1];
}
int query(int i, int l, int h, int ql, int qh)
{
if (h <= ql || qh <= l)
return 0;
if (l <= ql && qh <= h)
return v[i];
int m = (h - l) / 2 + l;
return query(2 * i, l, m, ql, qh) + query(2 * i + 1, m, h, ql, qh);
}
int query(int l, int h)
{
return query(1, 0, n, l, h);
}
SegTree() { }
SegTree(int sz)
{
n = 1;
while (n < sz)
n *= 2;
v = vi(2 * n + 1, 0);
}
};
int n;
SegTree st;
set<int> nl;
map<int, vi> qr;
int llc = 0;
int res = -1;
vi ask2(int i)
{
if (qr.count(i))
return qr[i];
qr[i] = ask(i);
return qr[i];
}
int cask(int i)
{
while (nl.count(i))
i++;
if (i >= n)
i--;
while (nl.count(i))
i--;
auto p = ask2(i);
if (p[0] + p[1] == 0)
res = i;
if (p[0] + p[1] < llc) {
nl.insert(i);
st.update(i, 1);
return 2;
}
int l = p[0] - st.query(0, i);
int r = p[1] - st.query(i, n);
return l < r;
}
int find_best(int n_)
{
n = n_;
st = SegTree(n);
for (int i = 0; i < min(n, 500); i++) {
auto p = ask2(i);
llc = max(llc, p[0] + p[1]);
if (p[0] + p[1] == 0)
return i;
}
while (res == -1) {
int l = 0;
int h = n;
while (l < h - 1) {
int m = (h - l) / 2 + l;
int r = cask(m);
if (r == 2)
break;
if (!r)
h = m;
else
l = m;
}
}
return res;
}
