#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int fen[MAXN],sp[MAXN][20];
vector< pair<int,int> > vq[MAXN];
set<int> st;
int getlog(long long n) { return 63-__builtin_clzll(n); }
void update(int i,int n,int val) { for(;i<=n;i+=i&-i) fen[i]+=val; }
int get(int i) { int ans=0;for(;i;i-=i&-i) ans+=fen[i];return ans; }
int walk(int n,int val) { int ans=0;for(int i=getlog(n);i+1;i--) if(ans+(1<<i)<=n&&val>=fen[ans+(1<<i)]) val-=fen[ans+=(1<<i)];return ans+1; }
int rmq(int l,int r)
{
int lg=getlog(r-l+1);
return max(sp[l][lg],sp[r-(1<<lg)+1][lg]);
}
int GetBestPosition(int N,int C,int r,int *K,int *S,int *E)
{
vector<int> L,R;
for(int i=1;i<N;i++)
{
update(i,N-1,1);
sp[i][0]=K[i-1];
}
for(int j=1;(1<<j)<N;j++) for(int i=1;i<=N-(1<<j);i++) sp[i][j]=max(sp[i][j-1],sp[i+(1<<(j-1))][j-1]);
for(int i=0;i<C;i++)
{
int lt=walk(N-1,S[i]),rt=walk(N-1,E[i])-1;
L.push_back(lt),R.push_back(rt);
lt=walk(N-1,S[i]+1);
while(lt<=rt) update(lt,N-1,-1),lt=walk(N-1,S[i]+1);
int f=rmq(lt,rt);
vq[lt].push_back({i,f<r}),vq[rt+2].push_back({-i,f<r});
}
for(int i=1;i<=N;i++) fen[i]=0;
int ans=0;
for(int i=1;i<=N;i++)
{
for(auto v:vq[i]) if(v.second)
{
if(v.first>0) update(v.first,N,1);
else update(-v.first,N,-1);
}
else
{
if(v.first>0) st.insert(v.first);
else st.erase(-v.first);
}
if(st.empty()) ans=max(ans,get(N));
else ans=max(ans,get(*st.begin()));
}
return ans;
}
