#include <bits/stdc++.h>
using namespace std;
const int N = (int) 1e5 + 7;
int aib[N], my_n;
void clr() {
for (int i = 1; i <= my_n; i++) {
aib[i] = 0;
}
}
void add(int i, int x) {
while (i <= my_n) {
aib[i] += x;
i += i & (-i);
}
}
int get(int i) {
int sol = 0;
while (i) {
sol += aib[i];
i -= i & (-i);
}
return sol;
}
int fnd(int k) {
int init_k = k;
int pos = 0, step = (1 << 20);
while (step) {
if (pos + step <= my_n && aib[pos + step] < k) {
pos += step;
k -= aib[pos];
}
step /= 2;
}
assert(get(pos + 1) == init_k);
return pos + 1;
}
int a[N], nxt2[N];
int GetBestPosition(int n, int cnt, int my_rank, int *init_ranks, int *st, int *dr) {
/// example -> solution = 1
my_n = n;
clr();
for (int i = 1; i <= n; i++) {
add(i, 1);
}
for (int i = cnt; i >= 1; i--) {
st[i] = st[i - 1] + 1;
dr[i] = dr[i - 1] + 1;
}
my_rank++;
for (int i = n - 1; i >= 1; i--) {
init_ranks[i] = init_ranks[i - 1] + 1;
}
st[0] = dr[0] = init_ranks[0] = 0;
int sz = n;
for (int i = 1; i <= cnt; i++) {
int X = st[i], Y = dr[i];
if (dr[i] == sz) {
dr[i] = n;
} else {
dr[i] = fnd(dr[i] + 1) - 1;
}
st[i] = fnd(st[i]);
for (int j = Y; j > X; j--) {
add(fnd(j), -1);
sz--;
}
}
for (int i = 1; i < n; i++) {
if (init_ranks[i] < my_rank) {
init_ranks[i] = 0;
} else {
assert(init_ranks[i] > my_rank);
init_ranks[i] = 2;
}
}
int best = -1, sol = -1;
for (int p = 1; p <= n; p++) {
int cur = 0;
for (int i = 1; i < p; i++) {
a[i] = init_ranks[i];
}
a[p] = 1;
for (int i = p + 1; i <= n; i++) {
a[i] = init_ranks[i - 1];
}
nxt2[n + 1] = n + 1;
for (int i = n; i >= 1; i--) {
if (a[i] == 2) {
nxt2[i] = i;
} else {
nxt2[i] = nxt2[i + 1];
}
}
for (int i = 1; i <= cnt; i++) {
if (nxt2[st[i]] <= dr[i]) {
break;
}
cur += (st[i] <= p && p <= dr[i]);
}
if (cur > best) {
best = cur;
sol = p;
}
}
assert(sol != -1);
return sol - 1;
}
