#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 200005;
int n;
int t[N * 4];
int u[N];
void ubd(int tl, int tr, int x, int y, int pos)
{
if (tl == tr)
{
t[pos] += y;
return;
}
int m = (tl + tr) / 2;
if (x <= m)
ubd(tl, m, x, y, pos * 2);
else
ubd(m + 1, tr, x, y, pos * 2 + 1);
t[pos] = t[pos * 2] + t[pos * 2 + 1];
}
int q;
int qry(int tl, int tr, int l, int r, int pos)
{
if (l > r)
return -1;
int m = (tl + tr) / 2;
if (tl == l && tr == r)
{
if (t[pos] < q)
{
q -= t[pos];
return -1;
}
if (tl == tr)
return tl;
}
int u = qry(tl, m, l, min(m, r), pos * 2);
if (u != -1)
return u;
return qry(m + 1, tr, max(m + 1, l), r, pos * 2 + 1);
}
int m;
const int k = 20;
int p[N][k];
int ul[N], ur[N];
int pr[N];
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E)
{
n = N;
for (int i = 0; i < n; ++i)
{
u[i] = i;
ubd(0, n - 1, i, 1, 1);
ul[i] = i;
ur[i] = i;
}
m = n;
for (int ii = 0; ii < C; ++ii)
{
vector<int> v;
int l = S[ii];
int r = E[ii];
q = l + 1;
v.push_back(qry(0, n - 1, 0, n - 1, 1));
for (int i = 0; i < r - l; ++i)
{
q = 1;
v.push_back(qry(0, n - 1, v.back() + 1, n - 1, 1));
}
ul[m] = ul[u[v[0]]];
ur[m] = ur[u[v.back()]];
for (int i = 0; i < sz(v); ++i)
{
p[u[v[i]]][0] = m;
}
u[v[0]] = m;
for (int i = 1; i < sz(v); ++i)
{
ubd(0, n - 1, v[i], -1, 1);
}
m++;
}
p[m - 1][0] = m - 1;
for (int x = m - 1; x >= 0; --x)
{
for (int i = 1; i < k; ++i)
{
p[x][i] = p[p[x][i - 1]][i - 1];
}
}
if (R == n - 1)
{
return 0;
}
for (int i = 0; i < n - 1; ++i)
{
if (i)
pr[i] = pr[i - 1];
if (K[i] > R)
pr[i]++;
}
int anss = -1;
int ans = -1;
for (int s = 0; s < n; ++s)
{
int x = s;
int yans = 0;
for (int i = k - 1; i >= 0; --i)
{
int l = ul[p[x][i]];
int r = ur[p[x][i]];
--r;
int s = pr[r];
if (l)
s -= pr[l - 1];
if (!s)
{
yans += (1 << i);
x = p[x][i];
}
}
if (yans > ans)
{
ans = yans;
anss = s;
}
}
return anss;
}
