#include <bits/stdc++.h>
#define ll long long
#define loop(i, a, b) for(ll i=a;i<b;++i)
#define pool(i, a, b) for(ll i=a-1;i>=b;--i)
#define fore(i, a) for(auto&& i:a)
#define fi first
#define se second
#define ps(a) push_back(a)
#define pb(a) pop_back(a)
#define eb(...) emplace_back(__VA_ARGS__)
#define sc scanf
#define vc vector
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(), a.end()
#define llmax LLONG_MAX/2
#define llmin -LLONG_MAX/2
using namespace std;
#define par pair<ll, ll>
#define ld long double
#define mod 998244353
struct segtr{
ll n;
vc<ll> sum;
void build(ll l, ll r, ll no=1){
if(l+1==r) sum[no]=1;
else{
ll mid=(l+r)/2;
build(l, mid, 2 * no);
build(mid, r, 2 * no + 1);
sum[no] = sum[2 * no] + sum[2 * no + 1];
}
}
segtr(ll n_){
n=n_;
sum.resize(4 * n);
build(0, n);
}
ll findkth(ll kth, ll add, ll l, ll r, ll no=1){
if(l+1==r){
sum[no]+=add;
return l;
}
else{
ll mid=(l+r)/2, ret;
if(kth<=sum[2 * no]) ret=findkth(kth, add, l, mid, no * 2);
else ret=findkth(kth-sum[2 * no], add, mid, r, no * 2 +1);
sum[no] = sum[2 * no] + sum[2 * no + 1];
return ret;
}
}
};
int GetBestPosition(int n, int c, int r, int *k, int *s, int *e){
segtr sg(n);
vc<vc<ll>> tredg(n);
vc<ll> kdo(n);
vc<ll> dp(n, 0), vseb(n, r), po(n), best(n);
loop(i, 0, n){
kdo[i]=i;
if(i<n-1)po[i]=k[i];
else po[i]=0;
best[i]=i;
}
loop(i, 0, c){
// ustvari novga
ll nov=dp.size();
dp.ps(0); vseb.ps(r);po.ps(0); tredg.ps({}), best.ps(0);
pool(j, e[i]+1, s[i]){
ll ind = sg.findkth(j+1, -(j!=s[i]), 0, n);
tredg[nov].ps(kdo[ind]);
if(j==s[i]) kdo[ind]=nov;
else kdo[ind]=-1;
}
reverse(all(tredg[nov]));
loop(j, 0, tredg[nov].size()){
ll v=tredg[nov][j];
po[nov]=max(po[nov], po[v]);
if(j+1==tredg[nov].size()) vseb[nov]=max(vseb[nov], vseb[v]);
else vseb[nov]=max(vseb[nov], po[v]);
}
//cout << po[nov]<<endl;
fore(v, tredg[nov]) if(dp[nov] < dp[v] + (vseb[nov]<=r)){
dp[nov] = dp[v] + (vseb[nov]<=r);
best[nov]=best[v];
}
}
return best.back();
}
