#include <algorithm>
#define MAXN 100009
#define MAXP 265000
int aint[MAXP], t[MAXN];
int val[MAXN], v[MAXN], calc[MAXN];
int best[MAXN], l[MAXN], r[MAXN];
int N, R, rez, left, right, cnt, poz;
void dfs(int p, int st, int dr) {
aint[p] = dr - st + 1;
if (st < dr) {
int m = (st + dr) / 2;
dfs(2 * p, st, m);
dfs(2 * p + 1, m + 1, dr);
}
}
void update(int p, int st, int dr) {
if (st == dr)
aint[p] = val[st] != -1;
else {
int m = (st + dr) / 2;
if (poz <= m) update(2 * p, st, m);
else update(2 * p + 1, m + 1, dr);
aint[p] = aint[2 * p] + aint[2 * p + 1];
}
}
void query(int p, int st, int dr) {
if (st == dr)
poz = st;
else {
int m = (st + dr) / 2;
if (cnt <= aint[2 * p])
query(2 * p, st, m);
else {
cnt -= aint[2 * p];
query(2 * p + 1, m + 1, dr);
}
}
}
void DFS(int p, int st, int dr) {
if (st == dr)
aint[p] = v[st];
else {
int m = (st + dr) / 2;
DFS(2 * p, st, m);
DFS(2 * p + 1, m + 1, dr);
aint[p] = std::max(aint[2 * p], aint[2 * p + 1]);
}
}
void UPDATE(int p, int st, int dr) {
if (st == dr)
aint[p] = v[st];
else {
int m = (st + dr) / 2;
if (left <= m) UPDATE(2 * p, st, m);
if (m < right) UPDATE(2 * p + 1, m + 1, dr);
aint[p] = std::max(aint[2 * p], aint[2 * p + 1]);
}
}
void QUERY(int p, int st, int dr) {
if (left <= st && dr <= right)
rez = std::max(rez, aint[p]);
else {
int m = (st + dr) / 2;
if (left <= m) QUERY(2 * p, st, m);
if (m < right) QUERY(2 * p + 1, m + 1, dr);
}
}
void solve(int x) {
rez = -1;
left = l[x];
right = r[x];
QUERY(1, 0, N - 1);
if (best[x] == rez)
return ;
best[x] = rez;
if (t[x] != -1)
solve(t[x]);
if (best[x] == R) {
calc[x] = 1;
if (t[x] != -1)
calc[x] += calc[t[x]];
} else
calc[x] = 0;
}
int GetBestPosition(int ceecunumarulasta, int C, int darcuastalalaltcei, int *K, int *S, int *E) {
N = ceecunumarulasta;
R = darcuastalalaltcei;
for (int i = 0; i < N; i++)
val[i] = i, l[i] = i, r[i] = i;
dfs(1, 0, N - 1);
for (int i = 0; i < N + C; i++)
t[i] = -1;
for (int i = 0; i < C; i++) {
cnt = S[i] + 1;
query(1, 0, N - 1);
int pos = poz;
l[i + N] = l[val[poz]];
t[val[poz]] = i + N;
val[poz] = -1;
update(1, 0, N - 1);
int u = E[i] - S[i];
while (u > 0) {
u--;
cnt = S[i] + 1;
query(1, 0, N - 1);
t[val[poz]] = i + N;
r[i + N] = r[val[poz]];
val[poz] = -1;
update(1, 0, N - 1);
}
val[poz] = i + N;
update(1, 0, N - 1);
}
for (int i = 0; i < N - 1; i++)
v[i] = K[i];
v[N - 1] = R;
DFS(1, 0, N - 1);
for (int i = C + N - 1; i >= 0; i--) {
rez = -1;
left = l[i];
right = r[i];
QUERY(1, 0, N - 1);
best[i] = rez;
if (best[i] == R) {
calc[i] = 1;
if (t[i] != -1)
calc[i] += calc[t[i]];
}
}
int ans = calc[N - 1], sol = N - 1;
for (int i = N - 2; i >= 0; i--) {
v[i + 1] = v[i];
v[i] = R;
left = i;
right = i + 1;
UPDATE(1, 0, N - 1);
solve(i + 1);
solve(i);
if (calc[i] >= ans)
ans = calc[i], sol = i;
}
return sol;
}
