#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int MAXV = 3e5;
//vector<int> con[MAXV];
int parent[MAXV];
int anc[MAXV][20];
pair<int,int> pozs[MAXV];
int aib[MAXV];
int qry(int poz)
{
poz+=2;
int aux=0;
for(int i=poz;i>0;i-=(i&(-i)))
aux+=aib[i];
return aux;
}
void upd(int poz, int newv)
{
poz+=2;
for(int i=poz;i<MAXV;i+=(i&(-i)))
aib[i]+=newv;
}
int get_kth(int k)
{
int st=0,dr=MAXV-5,ans=-1;
while(st<=dr)
{
int mij=(st+dr)/2;
if(qry(mij) >= k)
{
ans = mij;
dr = mij-1;
}
else
st = mij+1;
}
assert(ans!=-1);
return ans;
}
int myid[MAXV];
int tole[MAXV],tori[MAXV];
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E)
{
for(int i=0;i<N;i++)
{
myid[i] = i;
pozs[i] = {i,i};
upd(i,+1);
parent[i] = -1;
}
for(int i=0;i<C;i++)
{
pozs[N+i] = {INF, -1};
for(int pas=0;pas<E[i]-S[i]+1;pas++)
{
int poz = get_kth(S[i]+1);
//cerr<<N+i<<" "<<poz<<" poz\n";
upd(poz,-1);
parent[myid[poz]] = N+i;
pozs[N+i].first = min(pozs[N+i].first, pozs[myid[poz]].first);
pozs[N+i].second = max(pozs[N+i].second, pozs[myid[poz]].second);
}
parent[N+i] = -1;
myid[pozs[N+i].first] = N+i;
upd(pozs[N+i].first, +1);
}
assert(qry(N)==1);
//for(int i=0;i<N+C;i++)cerr<<i<<": "<<pozs[i].first<<" "<<pozs[i].second<<" parent: "<<parent[i]<<"\n";
for(int i=0;i<N+C;i++)
anc[i][0]=parent[i];
for(int p=1;p<20;p++)
for(int i=0;i<N+C;i++)
{
if(anc[i][p-1]==-1)
anc[i][p]=-1;
else
anc[i][p] = anc[anc[i][p-1]][p-1];
}
tole[0] = -1;
for(int i=0;i<N-1;i++)
{
if(K[i] > R)
tole[i+1] = i;
else
tole[i+1] = tole[i];
}
tole[N] = tole[N-1];
tori[N] = N-1;
for(int i=N-2;i>=0;i--)
{
if(K[i] > R)
tori[i+1] = i;
else
tori[i+1] = tori[i+2];
}
tori[0] = tori[1];
int mxm=-1,unde=-1;
for(int i=0;i<N;i++)
{
int ple = tole[i] + 1;
int pri = tori[i+1];
int cur = i, cnt = 0;
for(int p=19;p>=0;p--)
{
if(anc[cur][p]!=-1 && pozs[anc[cur][p]].first >= ple && pozs[anc[cur][p]].second <= pri)
{
cur = anc[cur][p];
cnt += (1<<p);
}
}
//cerr<<parent[cur]<<" parent\n";
//cerr<<i<<" "<<cnt<<" cnt\n";
if(cnt > mxm)
{
mxm = cnt;
unde = i;
}
}
return unde;
}
