#include <cstring>
#include <iostream>
#include <utility>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
int sparsetable[100005][20];
int par[200005][20];
int crealnode[200005];
int segm[400005];
int cnode, csz;
std::pair<int, int> segs[300005];
void upd(int idx, int l, int r, int tgt, int val) {
if(l == r) {segm[idx] = val; return;}
int mid = (l + r) >> 1;
if(tgt <= mid) upd(idx*2+1, l, mid, tgt, val);
else upd(idx*2+2, mid+1, r, tgt, val);
segm[idx] = segm[idx*2+1] + segm[idx*2+2];
}
int qr(int idx, int l, int r, int getpos) {
if(!getpos) return l;
if(l == r) return l;
int mid = (l+r) >> 1;
if(segm[idx*2+1] < getpos) return qr(idx*2+2, mid+1, r, getpos - segm[idx*2+1]);
return qr(idx*2+1, l, mid, getpos);
}
int getmx(int l, int r) {
int lg2pls = 31 - __builtin_clz(r-l+1);
return max(sparsetable[l][lg2pls], sparsetable[r-(1<<lg2pls)+1][lg2pls]);
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
int cmx = 0, cpos = 0;
for(int i=0;i<N-1;i++) {
sparsetable[i][0] = K[i];
}
for(int ck=1;ck<20;ck++)
for(int i=0;i<N-1;i++)
if(i + (1<<(ck-1)) < N-1)
sparsetable[i][ck] = max(sparsetable[i][ck-1], sparsetable[i+(1<<(ck-1))][ck-1]);
cnode = N;
memset(par, -1, sizeof par);
for(int i=0;i<N;i++) {crealnode[i] = i; segs[i] = {i, i}; upd(0, 0, N-1, i, 1);}
for(int i=0;i<C;i++) {
segs[cnode] = {N+9, -9};
for(int cidx = E[i]; cidx > S[i]; cidx--) {
int res = qr(0, 0, N-1, cidx+1);
par[crealnode[res]][0] = cnode;
segs[cnode].first = min(segs[cnode].first, segs[crealnode[res]].first);
segs[cnode].second = max(segs[cnode].second, segs[crealnode[res]].second);
upd(0, 0, N-1, res, 0);
}
int res = qr(0, 0, N-1, S[i]+1);
par[crealnode[res]][0] = cnode;
segs[cnode].first = min(segs[cnode].first, segs[crealnode[res]].first);
segs[cnode].second = max(segs[cnode].second, segs[crealnode[res]].second);
crealnode[res] = cnode;
cnode++;
}
for(int i=0;i<cnode;i++) {
for(int ck=1;ck<20;ck++) {
if(par[i][ck-1] == -1) break;
par[i][ck] = par[par[i][ck-1]][ck-1];
}
}
for(int i=0;i<N;i++) {
//try inserting into i??
int cdep = 0, cnode = i;
for(int ck=19;ck>=0;ck--) {
if(par[cnode][ck] == -1) continue;
if(getmx(segs[par[cnode][ck]].first, segs[par[cnode][ck]].second-1) <= R) {
cnode = par[cnode][ck];
cdep += (1 << ck);
}
}
//std::cout << i << " -> " << cdep << " (" << cnode << ") " << '\n';
if(cmx < cdep) {
cmx = cdep;
cpos = i;
}
}
return cpos;
}
/*
g++ tournament.cpp grader.cpp -o tournament
5 3 3
1 0 2 4
1 3
0 1
0 1
*/
