#include "bits/stdc++.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
using namespace std;
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
#define inbuf_len 1 << 16
#define outbuf_len 1 << 16
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E);
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 1e5 + 10;
int st[17][MAXN];
int query(int l, int r) {
int k = 32 - __builtin_clz(r-l+1) - 1; return max(st[k][l], st[k][r - (1<<k) + 1]);
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
int dsu[N];
for(int i=0; i<N; i++) dsu[i] = i;
for(int i=0; i<C; i++) {
int lb = 0, rb = N - 1;
while(lb < rb) {
int mid = (lb + rb) >> 1;
if(dsu[mid] >= S[i]) rb = mid;
else lb = mid + 1;
}
int lb2 = 0, rb2 = N - 1;
while(lb2 < rb2) {
int mid = (lb2 + rb2 + 1) >> 1;
if(dsu[mid] <= E[i]) lb2 = mid;
else rb2 = mid - 1;
}
for(int j=lb + 1; j<=lb2; j++) dsu[j] = dsu[lb];
for(int j=lb2 + 1; j<N; j++) dsu[j] -= (E[i] - S[i]);
S[i] = lb, E[i] = lb2;
}
/*
for(int i=0; i<C; i++) {
cout << "Range #" << i <<": " << S[i] << " " << E[i] << "\n";
}
*/
int opt_cnt = 0, opt_id = 0;
for(int P=0; P<N; P++) {
vector<int> now;
for(int j=0; j<P; j++) now.push_back(K[j]);
now.push_back(R);
for(int j=P; j<N; j++) now.push_back(K[j]);
for(int j=0; j<N; j++) st[0][j] = now[j];
for(int j=1; j<17; j++) {
for(int k=0; k<N; k++) {
if(k + (1<<j) - 1 < N) {
st[j][k] = max(st[j-1][k], st[j-1][k + (1 << (j-1))]);
}
}
}
int ok = 0;
for(int j=0; j<C; j++) {
ok += (query(S[j], E[j]) == R);
}
if(ok > opt_cnt) {
opt_cnt = ok;
opt_id = P;
}
}
return opt_id;
}
