#include<bits/stdc++.h>
#define mem(x,i) memset(x,i,sizeof(x))
#define dbg(x) cerr<<#x<<" = "<<x<<'\n';
using namespace std;
int bit[5005], arr[5005], l[5005], r[5005], n, lgn, c;
int kth(int k){
int p = 0;
for(int i=lgn;i>=0;i--){
int np = p + (1<<i);
if(np <= n && bit[np] < k){
k -= bit[np];
p = np;
}
}
return p+1;
}
void add(int x,int val){
for(;x<=n;x+=x&-x) bit[x]+=val;
}
void init(){
mem(bit, 0);
for(int i=1;i<=n;i++) add(i, 1);
}
int solve(int x){
init();
int ans = 0;
for(int i=1;i<=c;i++){
//cout<<i<<": \n";
int mxid = kth(l[i]);
//cout<<mxid<<" ";
for(int j=l[i]+1;j<=r[i];j++){
int id = kth(l[i]+1);
//cout<<id<<" ";
if(arr[id] > arr[mxid]){
add(mxid, -1);
mxid = id;
}
else add(id, -1);
}
//cout<<'\n';
if(mxid == x) ans++;
}
return ans;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
n = N;
c = C;
lgn = __lg(n);
arr[1] = R;
for(int i=2;i<=n;i++) arr[i] = K[i-2];
for(int i=1;i<=c;i++) l[i] = S[i-1]+1, r[i] = E[i-1]+1;
int ans = 0, cur = solve(1);
for(int i=1;i<n;i++){
swap(arr[i], arr[i+1]);
int x = solve(i+1);
if(x > cur) ans = i, cur = x;
}
return ans;
}
