#include <bits/stdc++.h>
using namespace std;
const int N = 100010 , LOG = 19;
int seg[4 * N] , n , dp[LOG][N] , dp2[LOG][N] , root , low , high , res , mid , depth[N] , nxt[N] , pre[N] , cur[N] , tmp , l;
vector< int > g[N] ;
int build(int s,int e,int idx){
if(s == e) return seg[idx] = 1;
return seg[idx] = build(s,(s+e)/2,idx*2) + build((s+e)/2+1,e,idx*2+1);
}
int getsum(int s,int e,int idx,int l,int r){
if(s > r || e < l) return 0;
if(s >= l && e <= r) return seg[idx];
return getsum(s,(s+e)/2,idx*2,l,r) + getsum((s+e)/2+1,e,idx*2+1,l,r);
}
int update(int s,int e,int idx,int idx2){
if(s > idx2 || e < idx2) return seg[idx];
if(s == e) return seg[idx] = 0;
return seg[idx] = update(s,(s+e)/2,idx*2,idx2) + update((s+e)/2+1,e,idx*2+1,idx2);
}
int lob(int val){
low = 0 , high = n - 1 , res = n;
while(high >= low){
mid = (low + high) / 2;
if(getsum(0,n-1,1,0,mid) >= val){
res = mid;
high = mid - 1;
}
else
low = mid + 1;
}
return res;
}
set < int > st;
set < int > :: iterator it;
void DFS(int node,int prnt,int d){
depth[node] = d;
dp[0][node] = prnt;
dp2[0][node] = cur[node];
for(int i=0;i<(int)g[node].size();i++){
if(g[node][i] != prnt)
DFS(g[node][i],node,d + 1);
}
}
int LCA(int u,int v){
if(depth[u] > depth[v])
swap(u,v);
for(int k=LOG-1;k>=0;k--){
if(depth[u] - (1 << k) >= depth[v]){
u = dp[k][u];
}
}
if(u == v)
return u;
for(int k=LOG-1;k>=0;k--){
if(dp[k][u] != dp[k][v]){
u = dp[k][u];
v = dp[k][v];
}
}
return dp[0][u];
}
int get(int u,int v){
int s = 0;
for(int k=LOG-1;k>=0;k--){
if(depth[u] - (1 << k) >= depth[v]){
s += dp2[k][v];
v = dp[k][v];
}
}
return s;
}
int GetBestPosition(int nnnn, int C, int R, int *K, int *S, int *E) {
n = nnnn;
build(0,n-1,1);
for(int i=0;i<n;i++)
st.insert(i);
for(int i=0;i<C;i++){
S[i] = lob(S[i] + 1);
E[i] = lob(E[i] + 1);
cur[S[i]]++;
it = st.upper_bound(S[i]);
while(it != st.end() && *it <= E[i]){
g[*it].push_back(S[i]);
g[S[i]].push_back(*it);
update(0,n-1,1,*it);
st.erase(it);
it = st.upper_bound(S[i]);
}
}
assert(st.size() == 1);
it = st.lower_bound(0);
root = *it;
DFS(root,-1,0);
for(int k=1;k<LOG;k++){
for(int i=1;i<=n;i++){
if(dp[k-1][i] == -1)
dp[k][i] = -1;
else{
dp2[k][i] = dp2[k-1][i] + dp2[k-1][dp[k-1][i]];
dp[k][i] = dp[k-1][dp[k-1][i]];
}
}
}
pre[0] = -1;
for(int i=1;i<n-1;i++){
if(K[i-1] > R)
pre[i] = i - 1;
else
pre[i] = pre[i-1];
}
nxt[n-1] = n - 1;
for(int i=n-2;i>=0;i--){
if(K[i] > R)
nxt[i] = i;
else
nxt[i] = nxt[i + 1];
}
int bestidx = 0 ,mx = -1;
for(int i=0;i<n-1;i++){
tmp = get(i,root) + cur[root];
if(pre[i] != -1){
l = LCA(i,pre[i]);
tmp = min(tmp,get(i,l));
}
if(nxt[i] != n - 1){
l = LCA(i,nxt[i] + 1);
tmp = min(tmp,get(i,l));
}
if(tmp > mx){
mx = tmp;
bestidx = i;
}
}
return bestidx;
}
