#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;
tree<pair<int,int>,null_type,less<pair<int,int> >,rb_tree_tag,tree_order_statistics_node_update> t;
int stt[200005],ent[200005],ct,dp[20][200005],stree[800005];
vector<int> v[200005];
void dfs(int node)
{
for (int i=1;i<20;i++)
{
if (dp[i-1][node]!=-1)
dp[i][node]=dp[i-1][dp[i-1][node]];
}
stt[node]=++ct;
for (int u:v[node])
dfs(u);
ent[node]=ct;
}
void update(int node,int st,int en,int idx,int val)
{
if (st==en)
stree[node]=val;
else
{
int mid=(st+en)/2;
if (st<=idx && idx<=mid)
update(2*node,st,mid,idx,val);
else
update(2*node+1,mid+1,en,idx,val);
stree[node]=(stree[2*node]&stree[2*node+1]);
}
}
int query(int node,int st,int en,int l,int r)
{
if (en<l || st>r || r<l)
return 1;
if (l<=st && en<=r)
return stree[node];
int mid=(st+en)/2;
return (query(2*node,st,mid,l,r)&query(2*node+1,mid+1,en,l,r));
}
int get(int pos)
{
int ans=0,cur=pos;
for (int i=19;i>=0;i--)
{
if (dp[i][cur]!=-1 && query(1,1,ct,stt[dp[i][cur]],ent[dp[i][cur]]))
{
ans+=(1<<i);
cur=dp[i][cur];
}
}
return ans;
}
int GetBestPosition(int n,int c,int r,int *k,int *s,int *e)
{
memset(dp,-1,sizeof(dp));
for (int i=0;i<n;i++)
t.insert({i,i});
for (int i=0;i<c;i++)
{
int cnt=e[i]-s[i]+1,cur;
for (auto it=t.find_by_order(s[i]);cnt;cnt--)
{
auto tmp=it;
it++;
cur=tmp->first;
dp[0][tmp->second]=n+i;
t.erase(tmp);
}
t.insert({cur,n+i});
}
for (int i=0;i<n+c-1;i++)
v[dp[0][i]].push_back(i);
dfs(n+c-1);
for (int i=0;i<n+c;i++)
update(1,1,ct,stt[i],1);
for (int i=1;i<n;i++)
update(1,1,ct,stt[i],(k[i-1]<r));
int ans=get(0),pos=0;
for (int i=1;i<n;i++)
{
update(1,1,ct,stt[i],1);
update(1,1,ct,stt[i-1],(k[i-1]<r));
if (get(i)>ans)
{
ans=get(i);
pos=i;
}
}
return pos;
}
