#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
int s[MAXN], e[MAXN];
int seg[4 * MAXN], sum[MAXN];
int l[MAXN], r[MAXN], good[MAXN];
int dp[20][MAXN];
int n, c;
void build(int x, int lx, int rx){
if(lx == rx){
seg[x] = 1;
return;
}
int m = (lx + rx) / 2, lc = 2 * x, rc = 2 * x + 1;
build(lc, lx, m);
build(rc, m + 1, rx);
seg[x] = seg[lc] + seg[rc];
}
void update(int x, int lx, int rx, int l, int r){
if(rx < l || lx > r) return;
if(l <= lx && rx <= r){
seg[x] = 0;
return;
}
int m = (lx + rx) / 2, lc = 2 * x, rc = 2 * x + 1;
update(lc, lx, m, l, r);
update(rc, m + 1, rx, l, r);
seg[x] = seg[lc] + seg[rc];
}
int bs(int x, int lx, int rx, int val){
if(lx == rx) return lx;
int m = (lx + rx) / 2, lc = 2 * x, rc = 2 * x + 1;
if(seg[lc] >= val) return bs(lc, lx, m, val);
return bs(rc, m + 1, rx, val - seg[lc]);
}
int solve(int i){
// quanto eu consigo subir na árvore a partir da pos i
int r = 0;
for(int k=19; k>=0; k--){
if(good[dp[k][i]]){
i = dp[k][i];
r += (1 << k);
}
}
return r;
}
int GetBestPosition(int n_, int c_, int rnk, int *k, int *s_, int *e_){
n = n_, c = c_;
// indexando tudo para 1
for(int i=n; i>=1; i--) k[i] = (k[i - 1] < rnk ? 0 : 1);
for(int i=c; i>=1; i--) s[i] = s_[i - 1] + 1, e[i] = e_[i - 1] + 1;
build(1, 1, n);
for(int i=1; i<=n; i++){
l[i] = r[i] = 1; // folhas
sum[i] = sum[i - 1] + k[i];
}
set<pair<int, int>> active;
for(int i=1; i<=n; i++) active.insert({i, i});
int cur = n;
for(int i=1; i<=c; i++){
int sz = e[i] - s[i] + 1; // quantos caras quero tirar
s[i] = bs(1, 1, n, s[i]);
e[i] = bs(1, 1, n, e[i]);
update(1, 1, n, s[i] + 1, e[i]); // suponho que o primeiro cara ganhou
cur ++;
l[cur] = s[i], r[cur] = e[i]; // folha de menor e maior indice
vector<pair<int, int>> to_erase;
auto it = active.lower_bound({s[i], 0});
while((int) to_erase.size() < sz){
to_erase.push_back(*it);
it ++;
}
for(auto [x, i] : to_erase){
active.erase({x, i});
dp[0][i] = cur; // cur é pai de i
}
active.insert({s[i], cur});
}
// binary-lifting
dp[0][n + c] = 0;
for(int i=1; i<=n+c; i++){
good[i] = (s[r[i] - 1] - s[l[i]] == 0) || (l[i] == r[i]);
}
for(int k=1; k<20; k++){
for(int i=1; i<=n+c; i++){
dp[k][i] = dp[k - 1][dp[k - 1][i]];
}
}
pair<int, int> ans = {-1, 1e9};
for(int i=1; i<=n; i++){
int cur_ans = solve(i);
if(cur_ans > ans.first){
ans = {cur_ans, i};
} else if(cur_ans == ans.first){
ans.second = min(ans.second, i);
}
}
return ans.second - 1;
}
