#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
array<array<int, 2>, 4*MAXN> seg, lz;
void refresh(int pos, int ini, int fim, int type)
{
if (lz[pos][type] == 1) return;
lz[pos][type] = 1; seg[pos][type] = 0;
if (ini == fim) return;
int e = 2*pos, d = e+1;
lz[e][type] = lz[d][type] = 0;
}
void refresh(int pos, int ini, int fim)
{
refresh(pos, ini, fim, 0);
refresh(pos, ini, fim, 1);
}
void build(int pos, int ini, int fim)
{
if (ini == fim)
{
seg[pos] = lz[pos] = {1, 1};
return;
}
int m = (ini + fim) >> 1;
int e = 2*pos, d = e+1;
build(e, ini, m);
build(d, m+1, fim);
seg[pos] = {seg[e][0] + seg[d][0], seg[e][1] + seg[d][1]};
lz[pos] = {1, 1};
}
void update(int pos, int ini, int fim, int p, int q, int type)
{
refresh(pos, ini, fim);
if (q < ini || p > fim) return;
if (p <= ini && fim <= q)
{
lz[pos][type] = 0;
refresh(pos, ini, fim);
return;
}
int m = (ini + fim) >> 1;
int e = 2*pos, d = e+1;
update(e, ini, m, p, q, type);
update(d, m+1, fim, p, q, type);
seg[pos] = {seg[e][0] + seg[d][0], seg[e][1] + seg[d][1]};
}
int bb(int pos, int ini, int fim, int val, int type)
{
if (ini == fim) return ini;
int m = (ini + fim) >> 1;
int e = 2*pos, d = e+1;
if (val <= seg[e][type]) return bb(e, ini, m, val, type);
else return bb(d, m+1, fim, val-seg[e][type], type);
}
int GetBestPosition(int N, int C, int R, int K[], int S[], int E[])
{
build(1, 1, N);
for (int i = 0; i < C; i++)
{
S[i] = bb(1, 1, N, S[i]+1, 0); E[i] = bb(1, 1, N, E[i]+1, 1);
update(1, 1, N, S[i]+1, E[i], 0); update(1, 1, N, S[i], E[i]-1, 1);
}
vector<array<int, 20>> dp(N);
for (int i = 1; i < N; i++) dp[i][0] = K[i-1];
for (int k = 1; k < 20; k++)
for (int i = 1; i < N; i++)
dp[i][k] = max(dp[i][k-1], dp[min(N-1, i+(1<<(k-1)))][k-1]);
vector<pair<int, int>> sweep;
for (int i = 0; i < C; i++)
{
int tam = E[i]-S[i];
int k = 31 - __builtin_clz(tam);
int val = max(dp[S[i]][k], dp[E[i]-(1<<k)][k]);
if (val < R) sweep.emplace_back(S[i], 0), sweep.emplace_back(E[i], 1);
}
int resp = 0, aux = 0, respId = 1;
sort(sweep.begin(), sweep.end());
for (auto [x, t] : sweep)
{
aux += (t == 0 ? 1 : -1);
if (aux > resp) respId = x, resp = aux;
}
return respId-1;
}
