// #include "grader.h"
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<pair<pair<double,double>, int>, null_type, less<pair<pair<double,double>, int>>, rb_tree_tag,
tree_order_statistics_node_update> ordered_set;
vector<int> AdjList[200005];
int sz[200005];
int curNode = 1;
int N, C, R, *K, *S, *E;
int actualIdxToNode[100005];
int nodeToActualIdx[200005];
int idxToAdd, sizeToAdd, curIdx;
ordered_set st;
void addNode() {
if(st.empty()) st.insert({{0,1},1});
auto it = st.find_by_order(idxToAdd);
auto l = it->first.first;
auto r = it->first.second;
auto id = it->second;
st.erase(it);
double x = (r-l)/sizeToAdd;
for(int i = 0; i < sizeToAdd; i++) {
AdjList[id].push_back(++curNode);
st.insert({{l, l+x}, curNode});
l += x;
}
}
int curActualIdx = 0;
int depth[200005];
int kthAncestor[20][200005];
void getDepth(int u, int d) {
depth[u] = d;
if(AdjList[u].empty()) {
sz[u] = 1;
actualIdxToNode[curActualIdx] = u;
nodeToActualIdx[u] = curActualIdx++;
return;
}
for(auto v: AdjList[u]) {
sz[u] += sz[v];
kthAncestor[0][v] = u;
getDepth(v, d-1);
}
}
void calcKthAncestor() {
kthAncestor[0][1] = 0;
for(int i = 1+1; i <= curNode; i++)
for(int j = 1; j < 20; j++) {
kthAncestor[j][i] = kthAncestor[j-1][kthAncestor[j-1][i]];
if(kthAncestor[j][i]==0) break;
}
}
int lca(int a, int b) {
if(depth[a] < depth[b])
for(int j = 31-__builtin_clz(C-depth[a]); j >= 0; j--)
if(depth[a] + (1<<j) <= depth[b])
a = kthAncestor[j][a];
if(depth[b] < depth[a])
for(int j = 31-__builtin_clz(C-depth[b]); j >= 0; j--)
if(depth[b] + (1<<j) <= depth[a])
b = kthAncestor[j][b];
for(int j = 31-__builtin_clz(C-depth[a]); j >= 0; j--)
if(kthAncestor[j][a] != kthAncestor[j][b]) {
a = kthAncestor[j][a];
b = kthAncestor[j][b];
}
if(a != b) {
a = kthAncestor[0][a];
b = kthAncestor[0][b];
}
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;
ordered_set stt;
for(int i = C-1; i >= 0; i--) {
curIdx = 0;
idxToAdd = S[i];
sizeToAdd = E[i]-S[i]+1;
addNode();
if(i%50==0) {
stt.clear();
double l = 0;
double x = 1./(st.size());
for(auto p: st) {
p.first.first = l;
p.first.second = l+x;
l += x;
stt.insert(p);
}
swap(st, stt);
}
}
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;
}
