#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define sc second
#define sz(v) (int)v.size()
typedef pair<int,int> pii;
typedef tree< pii, null_type, less<pii>, rb_tree_tag,
tree_order_statistics_node_update> ordered_set;
const int MAXN = 1e5+5, MAX = 17;
int sparse[2*MAXN][MAX+5], seg[MAXN*4], v[MAXN];
vector<int> vl,vr;
ordered_set st;
void build(int node, int l, int r){
if(l == r){
seg[node] = v[l];
return;
}
int mid = (l+r)/2, e = node*2, d = node*2+1;
build(e,l,mid); build(d,mid+1,r);
seg[node] = max(seg[e],seg[d]);
}
void update(int node, int l, int r, int i, int x){
if(i < l || r < i)return;
if(l == r){
seg[node] = x;
return;
}
int mid = (l+r)/2, e = node*2, d = node*2+1;
update(e,l,mid,i,x); update(d,mid+1,r,i,x);
seg[node] = max(seg[e],seg[d]);
}
int query(int node, int l, int r, int i, int j){
if(j < l || r < i)return 0;
if(i <= l && r <= j)return seg[node];
int mid = (l+r)/2, e = node*2, d = node*2+1;
return max(query(e,l,mid,i,j), query(d,mid+1,r,i,j));
}
int GetBestPosition(int n, int c, int r, int *K, int *s, int *e) {
for(int i = 0; i < n; i++){
st.insert({i,i});
vl.push_back(i); vr.push_back(i);
v[i+1] = K[i];
}
v[0] = r;
build(1,0,n-1);
for(int i = 0; i < 2*n; i++)
for(int j = 0; j <= MAX; j++)sparse[i][j] = -1;
int novo = n;
for(int i = 0; i < c; i++){
int x = e[i]-s[i];
for(int j = 0; j <= x; j++){
auto it = st.find_by_order(s[i]);
if(j == 0)vl.push_back(it->fi);
if(j == x)vr.push_back(vr[it->sc]);
sparse[it->sc][0] = novo;
st.erase(it);
}
st.insert({vl[novo], novo});
novo++;
}
for(int j = 1; j <= 1; j++)
for(int i = 0; i < sz(vl); i++)
if(sparse[i][j-1] != -1)
sparse[i][j] = sparse[sparse[i][j-1]][j-1];
int ans = 0;
for(int i = 0; i < n; i++){
if(i != 0){
swap(v[i-1],v[i]);
update(1,0,n-1, i-1, v[i-1]);
update(1,0,n-1, i, v[i]);
}
int cur = i, qtd = 0;
for(int j = MAX; j >= 0; j--){
if(sparse[cur][j] == -1)continue;
int mx = query(1,0,n-1, vl[sparse[cur][j]], vr[sparse[cur][j]]);
if(mx == r){
qtd += (1<<j);
cur = sparse[cur][j];
}
}
ans = max(ans,qtd);
}
return ans;
}
