#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
constexpr bool typetest = 0;
constexpr int N = 2e5 + 5;
struct Segmentree
{
int st[N * 4], lazy[N * 4];
void Build(int id, int l, int r)
{
if (l == r)
{
st[id] = 1;
lazy[id] = -1;
return;
}
Build(id << 1, l, (l + r) / 2);
Build(id << 1 | 1, (l + r) / 2 + 1, r);
st[id] = st[id << 1] + st[id << 1 | 1];
lazy[id] = -1;
}
void Push(int id, int l, int r)
{
if (lazy[id] != -1)
{
int mid = (l + r) / 2;
st[id << 1] = (mid - l + 1) * lazy[id];
lazy[id << 1] = lazy[id];
st[id << 1 | 1] = (r - mid) * lazy[id];
lazy[id << 1 | 1] = lazy[id];
lazy[id] = -1;
}
}
void Update(int id, int l, int r, const int &a, const int &b, const int &v)
{
if (l > b || r < a)
return;
if (l >= a && r <= b)
{
st[id] = (r - l + 1) * v;
lazy[id] = v;
return;
}
Push(id, l, r);
Update(id << 1, l, (l + r) / 2, a, b, v);
Update(id << 1 | 1, (l + r) / 2 + 1, r, a, b, v);
st[id] = st[id << 1] + st[id << 1 | 1];
}
int Find(int id, int l, int r, int v)
{
while (1)
{
if (l == r)
return l;
Push(id, l, r);
if (st[id << 1] >= v)
{
id <<= 1;
r = (l + r) / 2;
}
else
{
v -= st[id << 1];
id = id << 1 | 1;
l = (l + r) / 2 + 1;
}
}
return 0;
}
} f;
int last[N], id[N];
int GetBestPosition(int n, int c, int r, int *k, int *s, int *e)
{
f.Build(1, 1, n);
for (int i = 1; i <= n; ++i)
last[i] = i;
for (int i = 0; i < c; ++i)
{
*(s + i) = f.Find(1, 1, n, ++*(s + i));
*(e + i) = last[f.Find(1, 1, n, ++*(e + i))];
last[*(s + i)] = *(e + i);
f.Update(1, 1, n, *(s + i) + 1, *(e + i), 0);
id[i] = i;
}
sort(id, id + c, [&](const int &x, const int &y)
{ return *(s + x) < *(s + y) || (*(s + x) == *(s + y) && *(e + x) < *(e + y)); });
vector<pair<int, int>> v;
v.reserve(n);
for (int i = 0, j = 0; i < n - 1; ++i)
{
while (j < n - 1 && (k[i] <= r) == (k[j] <= r))
++j;
if (k[i] <= r)
v.emplace_back(i + 1, j + 1);
i = j - 1;
}
sort(v.begin(), v.end(), greater<pair<int, int>>());
priority_queue<int> x;
pair<int, int> u = {0, 0};
int z = c - 1;
for (auto i : v)
{
while (~z && *(s + id[z]) >= i.first)
{
x.emplace(*(e + id[z]));
--z;
}
while (x.size() && x.top() > i.second)
x.pop();
u = max(u, make_pair((int)x.size(), i.first - 1));
}
return u.second;
}
