#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;
template<class T>
struct rbt: tree<T,int,less<T>,
rb_tree_tag,tree_order_statistics_node_update>{};
typedef pair<int,int> pii;
#define fi first
#define se second
#define SZ 666666
rbt<pii> s; int fa[SZ];
pii gs[SZ]; int gn=0,su[SZ];
vector<int> ch[SZ];
int ans=0;
void dfs(int t,int d=0,int s=0)
{
s+=(su[gs[t].se]-su[gs[t].fi]==0);
if(gs[t].fi==gs[t].se)
// cout<<gs[t].fi<<":"<<s<<"\n",
ans=max(ans,s-1);
for(auto c:ch[t]) dfs(c,d+1,s);
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E)
{
gn=ans=0; s.clear();
for(int i=0;i<N;++i)
gs[++gn]=pii(i,i),
fa[gn]=0,ch[gn].clear(),
s[pii(i,i)]=gn;
for(int i=0;i<N-1;++i)
su[i+1]=su[i]+(K[i]>=R);
for(int i=0;i<C;++i)
{
auto g=s.find_by_order(S[i]);
int L=g->fi.fi,R; ++gn;
fa[gn]=0; ch[gn].clear();
for(int j=1;j<=E[i]-S[i]+1;++j)
R=g->fi.se,fa[g->se]=gn,
ch[gn].push_back(g->se),
s.erase(g++);
gs[gn]=pii(L,R);
s[pii(L,R)]=gn;
}
dfs(gn); return ans;
}
