#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 2e5+5;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second
int anc[20][MAXN], l_range[MAXN], r_range[MAXN], val[MAXN], niv[MAXN], seg[2*MAXN];
vector<int> edges[MAXN];
void dfs(int x) {
for(int viz : edges[x]) {
niv[viz] = niv[x] + 1;
dfs(viz);
anc[0][viz] = x;
l_range[x] = min(l_range[x], l_range[viz]);
r_range[x] = max(r_range[x], r_range[viz]);
}
}
void build(int node, int l, int r) {
if(l == r) {
seg[node] = val[l];
return;
}
int mid = (l+r)/2;
build(2*node, l, mid);
build(2*node+1, mid+1, r);
seg[node] = max(seg[2*node], seg[2*node + 1]);
}
void update(int node, int l, int r, int ind, int new_val) {
if(l == r) {
seg[node] = new_val;
return;
}
int mid = (l+r)/2;
if(ind <= mid) update(2*node, l, mid, ind, new_val);
else update(2*node + 1, mid+1, r, ind, new_val);
seg[node] = max(seg[2*node], seg[2*node + 1]);
}
int query(int node, int l, int r, int p, int q) {
if(r < p or q < l) return -1;
if(p <= l and r <= q) return seg[node];
int mid = (l+r)/2;
return max(query(2*node,l,mid,p,q), query(2*node+1,mid+1,r,p,q));
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
vector<int> v(N);
for(int i = 0; i < N; i++) v[i] = l_range[i] = r_range[i] = i;
// Unica parte em O(N²) é a construção das arestas
const int Sqrt = 300;
vector<vector<int>> groups;
groups.pb({0});
for(int i = 1; i < N; i++) {
if(sz(groups.back()) == Sqrt) groups.pb({i});
else groups.back().pb(i);
}
for(int t = 0; t < C; t++) {
int s = S[t], e = E[t], add = 0;
for(int G = 0, tam = 0; G < sz(groups); G++) {
int l_inter = max(s, tam), r_inter = min(e, tam + sz(groups[G]) - 1);
int ini_size = sz(groups[G]);
if(l_inter > r_inter) continue;
l_inter -= tam;
r_inter -= tam;
for(int i = r_inter; i >= l_inter; i--) {
edges[N + t].pb(groups[G][i]);
if(!add and i == l_inter) break;
groups[G].erase(groups[G].begin() + i);
}
if(!add) groups[G][l_inter] = N + t, add = 1;
tam += ini_size;
}
l_range[N + t] = N-1;
}
dfs(N + C - 1); // construindo os intervalos
anc[0][N + C - 1] = N + C - 1;
for(int bit = 1; bit <= 16; bit++) // construindo os ancestrais
for(int i = 0; i < N + C; i++)
anc[bit][i] = anc[bit-1][anc[bit-1][i]];
val[0] = R;
for(int i = 1; i < N; i++) val[i] = K[i-1];
build(1, 0, N-1); // seg construida
int ans = -1, num_ans = -1;
for(int i = 0; i < N; i++) { // dar swap em i e i+1
int x = i;
for(int bit = 16; bit >= 0; bit--) {
if(query(1, 0, N-1, l_range[anc[bit][x]], r_range[anc[bit][x]]) == R) {
x = anc[bit][x];
}
}
if(niv[i] - niv[x] > num_ans) num_ans = niv[i] - niv[x], ans = i;
if(i == N-1) break;
swap(val[i], val[i+1]);
update(1, 0, N-1, i, val[i]);
update(1, 0, N-1, i+1, val[i+1]);
}
return ans;
}
