/**
* Author: Nicholas Winschel
* Created: 06.05.2023 14:53:52
**/
#include <bits/extc++.h>
using namespace std;
using ll=long long;
using db=long double;
template<class T> using V=vector<T>;
using vi = V<int>;
using vl = V<ll>;
using pi = pair<int,int>;
#define f first
#define s second
#define sz(x) (int)((x).size())
struct inter {
int l=0,r=0,id=0;
inter () = default;
inter (int l, int r, int id) : l(l), r(r), id(id) {}
};
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
using rope = __gnu_cxx::rope<int>;
rope r;
V<vi> c(N);
V<inter> is(N);
for (int i = 0; i < N; i++) {
is[i]=inter(i,i,i);
r.push_back(i);
}
for (int i = 0; i < C; i++) {
int j = c.size();
c.emplace_back();
for (int k = S[i]; k <= E[i]; k++) {
c[j].push_back(r[k]);
}
r.erase(S[i],E[i]-S[i]+1);
r.insert(S[i],j);
is.emplace_back(is[c[j][0]].l, is[c[j][sz(c[j])-1]].r, j);
}
vi ans(N+1);
vi cl(N),cr(N);
int cnt = 0;
for (int i = 0; i < N-1; i++) if (K[i] > R) {
cl[i+1]++;
cr[i]++;
cnt++;
}
for (int i = 1; i < N; i++) cl[i]+=cl[i-1];
for (int i = N-2; i >= 0; i--) cr[i]+=cr[i+1];
auto dfs = [&](int v, auto &&dfs) -> void {
if (v < N) return;
if (cl[is[v].l]+cr[is[v].r] == cnt) {
ans[is[v].l]+=1;
ans[is[v].r+1]-=1;
}
for (int i : c[v]) dfs(i, dfs);
};
dfs(sz(c)-1,dfs);
for (int i = 1; i <= N; i++) ans[i] += ans[i-1];
return max_element(ans.begin(),ans.begin()+N)-ans.begin();
}
