#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int MAXV = 3e5;
//vector<int> con[MAXV];
int parent[MAXV],maxsub[MAXV];
pair<int,int> pozs[MAXV];
int val[MAXV];
int getmax(int le, int ri)
{
int mxm=0;
for(int i=le;i<=ri;i++)
mxm = max(mxm, val[i]);
return mxm;
}
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 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";
int mxm=-1,unde=-1;
for(int i=0;i<N;i++)
{
int cntv=0;
for(int j=0;j<i;j++)
val[cntv++] = K[j];
val[cntv++] = R;
for(int j=i;j<N-1;j++)
val[cntv++] = K[j];
assert(cntv==N);
//for(int j=0;j<N;j++)cerr<<val[j]<<" ";cerr<<"\n";
int cur = i, cnt = 0;
while(parent[cur]!=-1 && getmax(pozs[parent[cur]].first, pozs[parent[cur]].second) == R)
{
cnt++;
cur = parent[cur];
}
//cerr<<parent[cur]<<" parent\n";
//cerr<<i<<" "<<cnt<<" cnt\n";
if(cnt > mxm)
{
mxm = cnt;
unde = i;
}
}
return unde;
}
