#include <bits/stdc++.h>
//#include "grader.h"
using namespace std;
#define LL long long
#define F first
#define S second
const int N = 1e6+10;
const LL INF = 1e9;
int a[N],l2[N],r2[N];
int par[N],sizes[N],nxt[N],vals[N],pr[N][30];
LL tree[N],lazy[N];
vector<int>adj[N];
pair<int,int>p[N];
void push(int v,int l,int r){
tree[v] += lazy[v];
if(l!=r){
lazy[v*2] += lazy[v];
lazy[v*2+1] += lazy[v];
}
lazy[v] = 0;
}
void update(int v,int tl,int tr,int l,int r,int val){
push(v,tl,tr);
if(tl>r||tr<l)
return ;
if(tl>=l&&tr<=r){
lazy[v] += val;
push(v,tl,tr);
return ;
}
int mid = (tl+tr)/2;
update(v*2,tl,mid,l,r,val);
update(v*2+1,mid+1,tr,l,r,val);
tree[v] = tree[v*2]+tree[v*2+1];
}
int get(int v,int tl,int tr,int val){
push(v,tl,tr);
if(tl==tr)
return tl;
int mid = (tl+tr)/2;
push(v*2,tl,mid);
push(v*2+1,mid+1,tr);
if(tree[v*2]>=val)
return get(v*2,tl,mid,val);
else
return get(v*2+1,mid+1,tr,val-tree[v*2]);
}
int find_set(int u){
if(par[u]==u)
return u;
return par[u] = find_set(par[u]);
}
void merge(int u,int v){
u = find_set(u);
v = find_set(v);
if(u==v)
return ;
if(sizes[u]<sizes[v])
swap(u,v);
par[v] = u;
sizes[u] += sizes[v];
nxt[u] = max(nxt[u],nxt[v]);
}
void make_val(int u,int val1){
u = find_set(u);
vals[u] = val1;
}
void dfs(int i,int pre){
pr[i][0] = pre;
for(int j=1;j<=20;j++)
pr[i][j] = pr[pr[i][j-1]][j-1];
for(auto x:adj[i])
if(x==pre)continue;
else dfs(x,i);
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
int n = N,n1 = N;
for(int i=1;i<n;i++)
a[i] = K[i-1];
a[n] = R;
a[0] = a[n+1] = INF;
for(int i=1;i<=n;i++){
par[i] = vals[i] = i;
sizes[i] = 1;
nxt[i] = i+1,p[i] = {i,i};
update(1,1,n,i,i,1);
}
for(int i=0;i<C;i++){
int l1 = S[i]+1,r1 = E[i]+1;
int cnt = l1,pos = get(1,1,n,l1);
vector<int>vec;
while(cnt<=r1){
vec.push_back(pos);
pos = nxt[find_set(pos)];
cnt++;
}
n1++;
for(int i=0;i<vec.size();i++)
adj[n1].push_back(vals[find_set(vec[i])]);
for(int i=0;i<vec.size()-1;i++)
merge(vec[i],vec[i+1]);
p[n1] = {vec[0],nxt[vec.back()]-1};
for(int i=vec.size()-1;i>=1;i--)
update(1,1,n,vec[i],vec[i],-1);
make_val(vec[0],n1);
}
stack<int>st;
st.push(0);
for(int i=1;i<=n;i++){
while(a[st.top()]<R)st.pop();
l2[i] = st.top();
while(a[st.top()]<a[i])st.pop();
st.push(i);
}
while(!st.empty())st.pop();
st.push(n+1);
for(int i=n;i>=1;i--){
while(a[st.top()]<R)st.pop();
if(a[i]>R)r2[i] = i;
else r2[i] = st.top();
while(a[st.top()]<a[i])st.pop();
if(i<n)
st.push(i);
}
dfs(n1,n1);
int ret = n-1,ans = 0;
for(int i=n;i>=1;i--){
int ans1 = 0;
int cur = i;
for(int j=20;j>=0;j--)
if(p[pr[cur][j]].F>l2[i]&&p[pr[cur][j]].S<=r2[i])
cur = pr[cur][j],ans1 += 1<<j;
if(ans1>=ans){
ans = ans1;
ret = i-1;
}
}
return ret;
}
