#include <stdio.h>
#include <time.h>
#include <iostream>
#include <stdio.h>
#include <assert.h>
#include <vector>
#include <utility>
using namespace std;
int all[1000005];
struct A
{
int l,r;
int nxl,nxr;
int con;
pair < int , int > ans;
int add;
int big;
}Node[1000005];
int now;
int LL[100005];
int RR[100005];
void UPD(int here)
{
Node[Node[here].nxl].add+=Node[here].add;
Node[Node[here].nxr].add+=Node[here].add;
Node[Node[here].nxl].ans.first+=Node[here].add;
Node[Node[here].nxr].ans.first+=Node[here].add;
Node[here].add=0;
}
pair < int , int > operator +(pair < int , int > a,pair < int , int > b)
{
if(a.first>b.first) return a;
if(a.first<b.first) return b;
return make_pair(a.first,min(a.second,b.second));
}
void build(int l,int r,int here)
{
Node[here].l=l;
Node[here].r=r;
Node[here].con=(r-l+1);
Node[here].ans=make_pair(0,l);
if(l==r)
{
Node[here].big=all[l];
return;
}
Node[here].nxl=now++;
Node[here].nxr=now++;
build(l,(l+r)/2,Node[here].nxl);
build((l+r)/2+1,r,Node[here].nxr);
Node[here].big=max(Node[Node[here].nxl].big,Node[Node[here].nxr].big);
}
int Find(int here,int con)
{
if(Node[here].l==Node[here].r) return Node[here].l;
if(con<=Node[Node[here].nxl].con) return Find(Node[here].nxl,con);
else return Find(Node[here].nxr,con-Node[Node[here].nxl].con);
}
int Find2(int l,int r,int here)
{
if(Node[here].l==Node[here].r) return Node[here].big;
if(r<=Node[Node[here].nxl].con) return Find2(l,r,Node[here].nxl);
else if(l>Node[Node[here].nxl].con) return Find2(l,r,Node[here].nxr);
else return max(Find2(l,(Node[here].l+Node[here].r)/2,Node[here].nxl),Find2((Node[here].l+Node[here].r)/2+1,r,Node[here].nxr));
}
void cha(int where,int here)
{
Node[here].con--;
if(Node[here].l==Node[here].r) return;
if(where<=(Node[here].l+Node[here].r)/2) cha(where,Node[here].nxl);
else cha(where,Node[here].nxr);
}
void cha2(int l,int r,int con,int here)
{
if(Node[here].l==l&&Node[here].r==r)
{
Node[here].add+=con;
Node[here].ans.first+=con;
return;
}
UPD(here);
if(r<=Node[Node[here].nxl].con) cha2(l,r,con,Node[here].nxl);
else if(l>Node[Node[here].nxl].con) cha2(l,r,con,Node[here].nxr);
else
{
cha2(l,(Node[here].l+Node[here].r)/2,con,Node[here].nxl);
cha2((Node[here].l+Node[here].r)/2+1,r,con,Node[here].nxr);
}
Node[here].ans=Node[Node[here].nxl].ans+Node[Node[here].nxr].ans;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E)
{
int ans=0,where=0,who,i,j,k,tt,big,how=0;
//printf("aa\n");
for(i=0;i<N-1;i++) all[i]=K[i];
//printf("aaa\n");
build(0,N-1,0);
//printf("cc\n");
for(i=0;i<C;i++)
{
//printf("aa %d\n",i);
LL[i]=Find(0,S[i]+1);
RR[i]=Find(0,E[i]+1);
for(j=S[i];j<E[i];j++) cha(Find(0,j+1),0);
//printf("bb %d\n",i);
}
//printf("aaaa\n");
for(i=0;i<C;i++)
{
//printf("aa %d\n",i);
if(Find2(LL[i],RR[i]-1,0)>=R) cha2(LL[i],RR[i],-1e9,0);
//printf("bb %d\n",i);
cha2(LL[i],RR[i],1,0);
//printf("cc %d\n",i);
if(Node[0].ans.first>ans)
{
ans=Node[0].ans.first;
where=Node[0].ans.second;
}
else if(Node[0].ans.first==ans) where=min(where,Node[0].ans.second);
}
return where;
}
