#include <stdio.h>
#include <time.h>
#include <iostream>
#include <stdio.h>
using namespace std;
struct A
{
int nxl,nxr;
int rnd;
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)
{
if(l==0) return r;
if(r==0) return l;
if(Node[l].rnd>Node[r].rnd)
{
Node[l].nxr=Merge(Node[l].nxr,r);
UPD(l);
return l;
}
else
{
Node[r].nxl=Merge(l,Node[r].nxl);
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;
}
}
void BFS(int here)
{
if(here==0) return;
BFS(Node[here].nxl);
printf("%d ",Node[here].here);
BFS(Node[here].nxr);
}
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;
Node[now].rnd=rand();
root=Merge(root,now);
now++;
}
Node[now].big=R;
Node[now].here=R;
Node[now].nxl=0;
Node[now].nxr=0;
Node[now].sz=1;
Node[now].rnd=rand();
root=Merge(root,now);
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;
Node[now].rnd=rand();
root=Merge(root,now);
now++;
}
for(j=0;j<C;j++)
{
t=Split(root,S[j]);
t2=Split(t.second,E[j]-S[j]+1);
//printf("aa %d %d %d\n",i,Node[t2.first].big,Node[t2.first].sz);
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;
Node[now].rnd=rand();
root=Merge(Merge(t.first,now),t2.second);
now++;
}
//printf("%d %d\n",i,tt);
if(tt>ans)
{
ans=tt;
where=i;
}
}
return where;
}
