#include <bits/stdc++.h>
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")
using namespace std;
using ll = long long;
using ii = pair<ll, ll>;
using vi = vector<int>;
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lb lower_bound
const int oo = 1000 * 1000 * 1000 + 7;
int LOG[5005], SP[5005][15];
vector<int> P;
int query(int i, int j) {
int K = LOG[j - i + 1];
return max(SP[i][K], SP[j - (1 << K) + 1][K]);
}
int GetBestPosition(int N, int C, int R,
int* K, int* S, int* E) {
int res = 0, pos = 0; P.resize(N);
for(int l = 0; l < N; l++) P[l] = l;
for(int l = 0; l < C; l++) {
int A = lower_bound(P.begin(), P.end(), S[l]) - P.begin();
int B = lower_bound(P.begin(), P.end(), E[l] + 1) - P.begin() - 1;
for(int i = A; i <= B; i++) P[i] = P[A];
for(int i = B + 1; i < N; i++) P[i] -= (E[l] - S[l]);
S[l] = A, E[l] = B;
}
LOG[1] = 0;
for(int l = 2; l < N; l++)
LOG[l] = LOG[l / 2] + 1;
for(int l = 0; l < N - 1; l++)
SP[l][0] = K[l];
for(int l = 1; l < 15; l++)
for(int i = 0; i + (1 << l) <= N; i++)
SP[i][l] = max(SP[i][l - 1], SP[i + (1 << (l - 1))][l - 1]);
for(int l = 0; l < N; l++) {
int best = 0;
for(int i = 0; i < C; i++) {
int lo = S[i], hi = E[i];
if(l > hi || l < lo) continue;
int A = -1, B = -1;
if(l > lo) A = query(S[i], l - 1);
if(l < hi) B = query(l, E[i] - 1);
A = max(A, B);
if(A < R) best++;
else break;
}
if(best > res)
res = best, pos = l;
}
return pos;
}
