#include <stdio.h>
#include <time.h>
#include <iostream>
#include <stdio.h>
#include <assert.h>
using namespace std;
struct A
{
int nxl,nxr;
int here;
int big,sz;
}Node[1000005];
int now=0;
void UPD(int here)
{
Node[here].sz=Node[Node[here].nxl].sz+Node[Node[here].nxr].sz+1;
Node[here].big=max(max(Node[Node[here].nxl].big,Node[Node[here].nxr].big),Node[here].here);
}
int Merge(int l,int r,int con)
{
if(l==0) return r;
if(r==0) return l;
if((long long) rand()*(long long) (Node[l].sz+Node[r].sz)<=(long long) RAND_MAX*(long long) Node[l].sz)
{
Node[l].nxr=Merge(Node[l].nxr,r,con+1);
UPD(l);
return l;
}
else
{
Node[r].nxl=Merge(l,Node[r].nxl,con+1);
UPD(r);
return r;
}
}
pair < int , int > Split(int here,int con)
{
pair < int , int > t;
if(here==0) return make_pair(0,0);
if(con<=Node[Node[here].nxl].sz)
{
t=Split(Node[here].nxl,con);
Node[here].nxl=t.second;
UPD(here);
t.second=here;
return t;
}
else
{
t=Split(Node[here].nxr,con-Node[Node[here].nxl].sz-1);
Node[here].nxr=t.first;
UPD(here);
t.first=here;
return t;
}
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E)
{
int ans=-1,where=-1,now=1,root=0,i,j,tt;
pair < int , int > t,t2;
//srand(time(NULL));
Node[0].sz=0;
Node[0].big=-1;
for(i=0;i<N;i++)
{
now=1;
root=0;
tt=0;
for(j=0;j<i;j++)
{
Node[now].big=K[j];
Node[now].here=K[j];
Node[now].nxl=0;
Node[now].nxr=0;
Node[now].sz=1;
root=Merge(root,now,0);
now++;
}
Node[now].big=R;
Node[now].here=R;
Node[now].nxl=0;
Node[now].nxr=0;
Node[now].sz=1;
root=Merge(root,now,0);
now++;
for(j=i;j<N-1;j++)
{
Node[now].big=K[j];
Node[now].here=K[j];
Node[now].nxl=0;
Node[now].nxr=0;
Node[now].sz=1;
root=Merge(root,now,0);
now++;
}
for(j=0;j<C;j++)
{
t=Split(root,S[j]);
t2=Split(t.second,E[j]-S[j]+1);
Node[now].big=Node[t2.first].big;
Node[now].here=Node[t2.first].big;
if(Node[now].big==R) tt++;
Node[now].nxl=0;
Node[now].nxr=0;
Node[now].sz=1;
root=Merge(Merge(t.first,now,0),t2.second,0);
now++;
}
if(tt>ans)
{
ans=tt;
where=i;
}
}
return where;
}
