#include <bits/stdc++.h>
using namespace std;
vector<int> AdjList[400005];
int sz[400005];
int curNode = 1;
int N, C, R, *K, *S, *E;
int actualIdxToNode[100005];
int nodeToActualIdx[100005];
void addNode(int id, int curIdx, int idxToAdd, int sizeToAdd) {
if(AdjList[id].empty()) {
for(int i = 0; i < sizeToAdd; i++) {
AdjList[id].push_back(++curNode);
sz[curNode] = 1;
}
} else {
for(auto v: AdjList[id]) {
if(curIdx + sz[v] <= idxToAdd) {
curIdx += sz[v];
} else {
addNode(v, curIdx, idxToAdd, sizeToAdd);
break;
}
}
}
sz[id] = 0;
for(auto v: AdjList[id])
sz[id] += sz[v];
}
int curActualIdx = 0;
void assignIdx(int id) {
if(sz[id] == 1) {
actualIdxToNode[curActualIdx] = id;
nodeToActualIdx[id] = curActualIdx++;
return;
}
for(auto v: AdjList[id])
assignIdx(v);
}
int depth[400005];
int kthAncestor[400005][20];
void getDepth(int u, int d) {
depth[u] = d;
for(auto v: AdjList[u]) {
kthAncestor[v][0] = u;
getDepth(v, d-1);
}
}
void calcKthAncestor() {
kthAncestor[1][0] = 0;
for(int i = 1+1; i <= curNode; i++)
for(int j = 1; j < 20; j++)
kthAncestor[i][j] = kthAncestor[kthAncestor[i][j-1]][j-1];
}
int lca(int a, int b) {
for(int j = 19; j >= 0; j--)
if(depth[a] + (1<<j) <= depth[b])
a = kthAncestor[a][j];
for(int j = 19; j >= 0; j--)
if(depth[b] + (1<<j) <= depth[a])
b = kthAncestor[b][j];
for(int j = 19; j >= 0; j--)
if(kthAncestor[a][j] != kthAncestor[b][j]) {
a = kthAncestor[a][j];
b = kthAncestor[b][j];
}
if(a != b) {
a = kthAncestor[a][0];
b = kthAncestor[b][0];
}
return a;
}
int closestToLeft[100005];
int closestToRight[100005];
int GetBestPosition(int N_, int C_, int R_, int *K_, int *S_, int *E_) {
N=N_, C=C_, R=R_;
K=K_, S=S_, E=E_;
sz[1] = 1;
for(int i = C-1; i >= 0; i--)
addNode(1, 0, S[i], E[i]-S[i]+1);
assignIdx(1);
getDepth(1,C);
calcKthAncestor();
closestToLeft[0] = -1;
for(int i = 1; i <= N; i++) {
closestToLeft[i] = closestToLeft[i-1];
if(K[i-1] > R)
closestToLeft[i] = i-1;
}
closestToRight[N-1] = -1;
for(int i = N-1-1; i >= 0; i--) {
closestToRight[i] = closestToRight[i+1];
if(K[i+1-1] > R)
closestToRight[i] = i+1;
}
int ans = -1;
int pos = -1;
for(int i = 0; i < N; i++) {
int a = 0;
if(closestToLeft[i] == -1) {
a = C-depth[actualIdxToNode[i]];
} else {
a = depth[lca(actualIdxToNode[i], actualIdxToNode[closestToLeft[i]])]-depth[actualIdxToNode[i]]-1;
}
int b = 0;
if(closestToRight[i] == -1) {
b = C-depth[actualIdxToNode[i]];
} else {
b = depth[lca(actualIdxToNode[i], actualIdxToNode[closestToRight[i]])]-depth[actualIdxToNode[i]]-1;
}
if(min(a,b) > ans) {
ans = min(a,b);
pos = i;
}
}
return pos;
}
