#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
#define endl "\n"
const int mxn=5000+5;
int n,q,k,dp[mxn][mxn];
vector<int>arr;
vector<pii>p,vt,p2;
int tree[4*mxn];
void build(int node,int l,int r){
if(l==r){
tree[node]=arr[l];
return;
}
int m=(l+r)/2;
build(2*node,l,m);
build(2*node+1,m+1,r);
tree[node]=max(tree[2*node],tree[2*node+1]);
}
int query(int node,int l,int r,int ql,int qr){
if(r<ql||l>qr) return -1;
if(ql<=l&&r<=qr) return tree[node];
int m=(l+r)/2;
int x=query(2*node,l,m,ql,qr);
int y=query(2*node+1,m+1,r,ql,qr);
return max(x,y);
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
n=N;
q=C;
k=R;
for(int i=0;i<n-1;i++){
arr.pb(K[i]);
}
for(int i=0;i<q;i++){
p.pb({S[i],E[i]});
}
for(int i=0;i<n;i++){
vt.pb({i,i});
}
for(int i=0;i<q;i++){
int l=p[i].F,r=p[i].S;
int a=1e9,b=-1e9;
for(int j=l;j<=r;j++){
a=min(a,vt[j].F);
b=max(b,vt[j].S);
}
p2.pb({a,b});
int say=r-l;
while(say--){
vt.erase(vt.begin()+l);
}
vt[l]={a,b};
}
for(int i=0;i<n-1;i++){
dp[i][i]=arr[i];
for(int j=i+1;j<n-1;j++){
dp[i][j]=max(arr[j],dp[i][j-1]);
}
}
build(1,0,n-2);
int ans=0,pl=0;
for(int i=0;i<n;i++){
int cnt=0;
for(auto [l,r]:p2){
if(i>=l&&i<=r){
int l1=l,r1=i-1;
int l2=i+1,r2=r;
int cur=-1;
if(r1>=l1){
cur=max(cur,dp[l1][r1]);
}
if(r2>=l2){
cur=max(cur,dp[l2-1][r2-1]);
}
if(k>cur){
cnt++;
}
}
}
if(cnt>ans){
ans=cnt;
pl=i;
}
}
return pl;
}
