#include <bits/stdc++.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define inbuf_len 1 << 16
#define outbuf_len 1 << 16
#define MAX 505000
std::vector<int> con[MAX];
int val[MAX];
int cur=32;
int posicao[MAX];
int alocar(void){
return cur++;
}
typedef std::pair<int,int> pii;
std::vector<int> v;
int contagem=0;
void gerar(int l,int r){
int count=0;
int alocado = alocar();
for(int i=0;i!=v.size();++i){
if(v[i]==-1){
continue;
}
if(count>=l&&count<=r){
con[v[i]].push_back(alocado);
con[alocado].push_back(v[i]);
if(count==l)v[i]=alocado;else {v[i]=-1;++contagem;}
}
++count;
}
if(contagem>350){
contagem=0;
std::vector<int> novo;
for(auto&x:v)if(x!=-1)novo.push_back(x);
v=novo;
}
}
const int inf = 1e9;
pii range[MAX];
int up[MAX][20];
pii dfs(int pos,int prev){
pii val = {inf,-inf};
up[pos][0]=prev;
for(int j=1;j!=20;++j){
up[pos][j]=up[up[pos][j-1]][j-1];
}
if(posicao[pos]){
int k = posicao[pos]-inf;
return range[pos]={k,k};
}
for(auto&x:con[pos]){
if(x==prev)continue;
auto __ = dfs(x,pos);
val.first=std::min(val.first,__.first);
val.second=std::max(val.second,__.second);
}
return range[pos]=val;
}
int tab[MAX*4];
void update(int t,int k,int la=0,int ra=MAX-1,int pos=1){
if(la>t||ra<t)return;
if(la==ra){
tab[pos]=k;
return;
}
int m = (la+ra)/2;
update(t,k,la,m,pos*2);
update(t,k,m+1,ra,(pos*2)+1);
tab[pos]=std::max(tab[pos*2],tab[(pos*2)+1]);
}
int query(int l,int r,int la=0,int ra=MAX-1,int pos=1){
if(la>r||ra<l)return -inf;
if(la>=l&&ra<=r){
return tab[pos];
}
int m = (la+ra)/2;
return std::max(query(l,r,la,m,pos*2),query(l,r,m+1,ra,(pos*2)+1));
}
int levitar(int pos,int levita){
for(int j=19;j!=-1;--j){
if(levita&(1<<j)){
pos=up[pos][j];
// std::cout<<up[pos][j]<<"\n";
}
}
return pos;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
///Primeira etapa: Gerar a arvore
for(int i=0;i!=N;++i){
int p = alocar();
v.push_back(p);
posicao[p] = inf + i;
if(i){
update(i,K[i-1]);
}else update(0,R);
}
for(int i=0;i!=C;++i){
gerar(S[i],E[i]);
}
range[0]={-inf,-inf};
int raiz = cur-1;
dfs(raiz,-1);
int best=0,pos=0;
for(int i=0;i!=N;++i){
int l=0,r=C;
while(l<r){
int m = (l+r+1)/2;
int posicao = levitar(32+i,m);
int valor = query(range[posicao].first,range[posicao].second);
// std::cout<<m<<" "<<posicao<<" "<<valor<<" "<<32+i<<" "<<range[posicao].first<<" "<<range[posicao].second<<"\n";
if(valor==R){
l=m;
}else r=m-1;
}
if(l>best){
// std::cout<<"show!\n";
best=l;
pos=i;
}
if(i!=N-1){
update(i,K[i]);
update(i+1,R);
}
}
return pos;
}
