#include <algorithm>
#include <string.h>
#include <vector>
using namespace std;
int plu(int a,int b)
{
return a+b;
}
int maa(int a,int b)
{
return max(a,b);
}
struct segtree
{
int N,treeN;
int stree[1<<10];
int (*fp)(int,int);
int ec;
void init(int M,int (*p)(int,int),int e)
{
fp=p;
ec=e;
fill(stree,stree+(1<<10),ec);
N=M;
for(treeN=1;treeN<N;treeN*=2);
}
void upd(int n,int k)
{
n+=treeN;
stree[n]=k;
while(n!=1)
{
n/=2;
stree[n]=fp(stree[n*2],stree[n*2+1]);
}
}
int ge(int s,int e,int qs,int qe,int i)
{
if(s>qe||qs>e)
return ec;
if(qs<=s&&e<=qe)
return stree[i];
return fp(ge(s,(s+e)/2,qs,qe,i*2),ge((s+e)/2+1,e,qs,qe,i*2+1));
}
int kth(int s,int e,int i,int k)
{
if(s==e)
return s;
if(stree[i*2]<=k)
return kth((s+e)/2+1,e,i*2+1,k-stree[i*2]);
return kth(s,(s+e)/2,i*2,k);
}
}ma,kth;
int to[10010];
int rs[10010];
int re[10000];
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E)
{
ma.init(N-1,maa,0);
kth.init(N+1,plu,0);
int i;
for(i=0;i<=N;i++)
{
kth.upd(i,1);
}
for(i=0;i<N-1;i++)
{
ma.upd(i,K[i]);
}
for(i=0;i<C;i++)
{
rs[i]=kth.kth(0,kth.treeN-1,1,S[i]);
re[i]=kth.kth(0,kth.treeN-1,1,E[i]+1)-1;
to[i]=ma.ge(0,ma.treeN-1,rs[i],re[i]-1,1);
int j;
for(j=S[i]+1;j<=E[i];j++)
{
kth.upd(kth.kth(0,kth.treeN-1,1,S[i]+1),0);
}
}
vector<pair<int,int>>x;
for(i=0;i<C;i++)
{
if(to[i]<R)
{
x.push_back({rs[i],1});
x.push_back({re[i]+1,-1});
}
}
sort(x.begin(),x.end());
pair<int,int>an={0,0};
int cu=0;
for(i=0;i<x.size();i++)
{
cu+=x[i].second;
an=max(an,{cu,-x[i].first});
}
return -an.second;
}
