#include <bits/stdc++.h>
using namespace std;
mt19937 mt(869120);
struct treap{
int pri,size,range_l,range_r,type;
treap *lch,*rch;
treap(int l,int r,int t){
lch=rch=NULL;
range_l=l;
range_r=r;
type=t;
pri=mt();
size=1;
}
treap(){
}
};
int size(treap *pt){
if(pt==NULL)return 0;
return pt->size;
}
treap* update(treap *pt){
pt->size=size(pt->lch)+size(pt->rch)+1;
return pt;
}
treap* merge(treap *l,treap *r){
if(l==NULL)return r;
else if(r==NULL)return l;
if(l->pri>r->pri){
l->rch=merge(l->rch,r);
return update(l);
}
else{
r->lch=merge(l,r->lch);
return update(r);
}
}
pair<treap*,treap*>split(treap* pt,int t){
if(pt==NULL)return{NULL,NULL};
if(t<=size(pt->lch)){
auto p=split(pt->lch,t);
pt->lch=p.second;
return {p.first,update(pt)};
}
else{
auto p=split(pt->rch,t-size(pt->lch)-1);
pt->rch=p.first;
return{update(pt),p.second};
}
}
void dfs(int &l,int &r,vector<int>&v,treap*pt){
if(pt==NULL)return;
l=min(l,pt->range_l);
r=max(r,pt->range_r);
if(pt->type!=-1){
v.push_back(pt->type);
}
dfs(l,r,v,pt->lch);
dfs(l,r,v,pt->rch);
}
int tree[1<<18],A[100000],P[100000],L[100000],R[100000],V[100000];
treap tre[200000];
treap *root;
int calc(int l,int r){
l+=1<<17;
r+=1<<17;
int a=-1;
while(l<=r){
a=max({a,tree[l],tree[r]});
l=(l+1)/2;
r=(r-1)/2;
}
return a;
}
int GetBestPosition(int N, int C, int T, int *K, int *S, int *E) {
for(int i=0;i<N-1;i++){
tree[i+(1<<17)]=K[i];
}
for(int i=(1<<17)-1;i;i--){
tree[i]=max(tree[i+i],tree[i+i+1]);
}
for(int i=0;i<N;i++){
tre[i]=treap(i,i,-1);
}
root=tre;
for(int i=1;i<N;i++){
root=merge(root,tre+i);
}
cout<<size(root)<<endl;
for(int i=0;i<C;i++){
auto p=split(root,E[i]+1);
auto pp=split(p.first,S[i]);
L[i]=0xE869120;
R[i]=-0xE869120;
vector<int>v;
dfs(L[i],R[i],v,pp.second);
tre[N+i]=treap(L[i],R[i],i);
root=merge(pp.first,merge(tre+N+i,p.second));
for(int j:v){
P[j]=i;
}
}
P[C-1]=C-1;
for(int i=C-1;i>=0;i--){
V[i]=V[P[i]]+(calc(L[i],R[i]-1)<T);
}
pair<int,int>p={0,0};
for(int i=0;i<C-1;i++){
p=max(p,{V[i],-L[i]});
}
return -p.second;
}
