//#include<bits/stdc++.h>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1e5+6;
const int lg=18;
int par[MAXN][lg];
vector<int>g[MAXN];
bool not_leaf[MAXN];
struct BIT
{
int fen[MAXN];
void update(int idx,int val)
{
idx++;
for(;idx<MAXN;idx+=idx&(-idx))
{
fen[idx]+=val;
}
}
int get_position(int idx)
{
idx++;
int ret=0;
for(;idx>0;idx-=idx&(-idx))
{
ret+=fen[idx];
}
return ret;
}
}real_positions1,real_positions2;
struct segment_tree
{
int tree[4*MAXN];
void build(int l,int r,int idx)
{
tree[idx]=MAXN;
if(l!=r)
{
int mid=(l+r)/2;
build(l,mid,idx*2);
build(mid+1,r,idx*2+1);
}
}
void update(int l,int r,int idx,int ql,int qr,int val)
{
if(l>qr)return;
if(r<ql)return;
if(l>=ql&&r<=qr)
{
tree[idx]=min(tree[idx],val);
return;
}
int mid=(l+r)/2;
update(l,mid,idx*2,ql,qr,val);
update(mid+1,r,idx*2+1,ql,qr,val);
}
int query(int l,int r,int idx,int q)
{
//cout<<l<<" "<<r<<" "<<idx<<" "<<q<<endl;
if(l>q)return MAXN;
if(r<q)return MAXN;
if(l==r)return tree[idx];
int mid=(l+r)/2;
return min(tree[idx],min(query(l,mid,idx*2,q),query(mid+1,r,idx*2+1,q)));
}
}t;
struct segment_tree1
{
int tree[4*MAXN];
void update(int l,int r,int idx,int q,int val)
{
if(l>q)return;
if(r<q)return;
if(l==r)
{
tree[q]=val;
return;
}
int mid=(l+r)/2;
update(l,mid,idx*2,q,val);
update(mid+1,r,idx*2+1,q,val);
tree[idx]=max(tree[idx*2],tree[idx*2+1]);
}
int query(int l,int r,int idx,int ql,int qr)
{
if(l>qr)return 0;
if(r<ql)return 0;
if(l>=ql&&r<=qr)return tree[idx];
int mid=(l+r)/2;
return max(query(l,mid,idx*2,ql,qr),query(mid+1,r,idx*2+1,ql,qr));
}
}t1;
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
vector<pair<int,int> >real;
//cout<<"?\n";
for(int i=1;i<N;i++)
{
real_positions1.update(i,1);
real_positions2.update(i,1);
}
//cout<<"?\n";
for(int i=0;i<C;i++)
{
int s1=real_positions1.get_position(S[i]);
int e1=real_positions2.get_position(E[i]);
real.push_back({s1,e1});
real_positions1.update(s1+1,E[i]-S[i]);
real_positions2.update(s1,E[i]-S[i]);
}
// down
/*for(auto xd:real)
{
cout<<xd.first<<" "<<xd.second<<endl;
}*/
//cout<<"?\n";
//reverse(real.begin(),real.end());
t.build(0,N-1,1);
t.update(0,N-1,1,real.back().first,real.back().second,real.size());
par[real.size()+1][0]=0;
for(int i=real.size()-2;i>=0;i--)
{
int br=t.query(0,N-1,1,real[i].first);
par[i+1][0]=br;
not_leaf[br]=1;
t.update(0,N-1,1,real[i].first,real[i].second,i+1);
}
// down
for(int step=1;step<lg;step++)
{
for(int i=1;i<=C;i++)
{
par[i][step]=par[par[i][step-1]][step-1];
}
}
/*for(int i=1;i<=C;i++)
{
cout<<"^^ "<<i<<" "<<par[i][0]<<endl;
}*/
for(int i=1;i<N;i++)
{
t1.update(0,N-1,1,i,K[i-1]);
}
int ans=0;
//down
for(int i=0;i<N;i++)
{
//cout<<i<<endl;
int x=t.query(0,N-1,1,i);
//
int d=0;
for(int j=lg-1;j>=0;j--)
{
//cout<<" "<<j<<endl;
//cout<<" "<<x<<" "<<j<<" "<<par[x][j]<<endl;
if(par[x][j]==0)continue;
int f=par[x][j]-1;
//cout<<" "<<real[f].first<<" "<<real[f].second<<" "<<t1.query(0,N-1,1,real[f].first,real[f].second)<<endl;
if(t1.query(0,N-1,1,real[f].first,real[f].second)>=R)
{
continue;
}
x=par[x][j];
d+=(1<<j);
}
//cout<<"?\n";
ans=max(ans,d);
if(i==N-1)continue;
//cout<<" -\n";
t1.update(0,N-1,1,i,K[i]);
if(i>N-10)return 0;
}
return ans;
}
/*
5 3 3
1
0
2
4
1 3
0 1
0 1
*/
