#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
using namespace std;
/*
5 3 3
1 0 2 4
1 3
0 1
0 1
*/
const int NMAX = 2e5 + 1;
vector <int> t(4 * NMAX), lazy1(4 * NMAX), lazy2(4 * NMAX);
void push1(int v){
if(lazy1[v]){
t[2 * v] += lazy1[v];
t[2 * v + 1] += lazy1[v];
lazy1[2 * v] += lazy1[v];
lazy1[2 * v + 1] += lazy1[v];
lazy2[2 * v] = lazy2[2 * v + 1] = lazy1[v] = 0;
}
}
void push2(int v){
if(lazy2[v]){
t[2 * v] = t[2 * v + 1] = lazy2[2 * v] = lazy2[2 * v + 1] = lazy2[v];
lazy2[v] = lazy1[2 * v] = lazy1[2 * v + 1] = 0;
}
}
int getfirst(int v, int l, int r, int val){
if(l == r){
if(t[v] < val) return -1;
return l;
}
push1(v);
push2(v);
int m = (l + r) / 2;
if(t[2 * v] >= val) return getfirst(2 * v, l, m, val);
return getfirst(2 * v + 1, m + 1, r, val);
}
void update1(int v, int l, int r, int st, int fin, int val){
if(l > fin || r < st) return;
if(l >= st && r <= fin){
lazy1[v] += val;
t[v] += val;
return;
}
push1(v);
push2(v);
int m = (l + r) / 2;
update1(2 * v, l, m, st, fin, val);
update1(2 * v + 1, m + 1, r, st, fin, val);
t[v] = max(t[2 * v], t[2 * v+ 1]);
}
void update2(int v, int l, int r, int st, int fin, int val){
if(l > fin || r < st) return;
if(l >= st && r <= fin){
lazy1[v] = val;
t[v] = val;
return;
}
push1(v);
push2(v);
int m = (l + r) / 2;
update2(2 * v, l, m, st, fin, val);
update2(2 * v + 1, m + 1, r, st, fin, val);
t[v] = max(t[2 * v], t[2 * v+ 1]);
}
void build(int v, int l, int r){
if(l == r){
t[v] = l;
return;
}
int m = (l + r) / 2;
build(2 * v, l, m);
build(2 * v + 1, m + 1, r);
t[v] = max(t[2 * v], t[2 * v + 1]);
}
vector <int> p(NMAX), sz(NMAX);
void make_set(int v){
p[v] = v;
sz[v] = 1;
return;
}
int find_set(int v){
if(p[v] == v) return v;
return p[v] = find_set(p[v]);
}
void union_sets(int a, int b){
a = find_set(a);
b = find_set(b);
if(a == b) return;
if(sz[a] < sz[b]) swap(a, b);
p[b] = a;
sz[a] += sz[b];
}
vector <int> bit(NMAX);
int lsb(int x){
return x & -x;
}
void add(int pos, int val){
while(pos < NMAX){
bit[pos] += val;
pos += lsb(pos);
}
}
int get(int pos){
int res = 0;
while(pos){
res += bit[pos];
pos -= lsb(pos);
}
return res;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
set <int> st;
for(int i = 0; i < N - 1; i++){
if(K[i] > R) st.insert(i);
}
vector <pii> vec;
vector <int> ans(N + 1, 1e9);
for(int i = 1; i <= N; i++){
auto it = st.upper_bound(i - 2);
if(it != st.end()) vec.pb({i, *it + 1});
if(it != st.begin()){
it--;
vec.pb({i, *it + 1});
}
}
int n = N;
build(1, 1, n);
vector <vector <int> > qv;
for(int i = 0; i < C; i++){
int x = S[i], y = E[i];
x++, y++;
vector <int> cur;
for(int i = x; i <= y; i++){
int v = getfirst(1, 1, n, i);
cur.pb(v);
}
int v = getfirst(1, 1, n, y + 1);
if(v == -1){
update2(1,1 , n, cur[0], n, x);
}
else{
update2(1, 1, n, cur[0], v - 1, x);
update1(1, 1, n, v, n, x - y);
}
qv.pb(cur);
}
/*for(int i = 0; i < C; i++){
for(int to : qv[i]){
cout << to << ' ';
}
cout << "\n";
}*/
vector <int> l(vec.size(), -1), r(vec.size(), C);
for(int j = 0; j < 18; j++){
vector <vector <int> > mid(n + 1);
for(int i = 0; i < vec.size(); i++){
int m = l[i] + r[i];
if(l[i] + 1 == r[i]) continue;
mid[m / 2].pb(i);
}
for(int i = 1; i<= n; i++) make_set(i);
for(int i = 0; i < C; i++){
for(int k = 1; k < qv[i].size(); k++) union_sets(qv[i][k], qv[i][k - 1]);
for(int to : mid[i]){
int x = vec[to].f, y = vec[to].s;
if(find_set(x) == find_set(y)) {
r[to] = i;
}
else l[to] = i;
}
}
}
for(int i = 0; i < vec.size(); i++){
auto to = vec[i].f;
ans[to] = min(ans[to], r[i]);
// cout << r[i] << ' ';
}
vector <vector <int> > vv(C);
for(int i = 1; i <= n; i++){
if(ans[i] < C)vv[ans[i]].pb(i);
}
int aa[n + 1];
fill(aa + 1, aa + n + 1, C);
for(int i = 0; i < C; i++){
add(S[i] + 1, 1);
add(E[i] + 2, -1);
for(int to : vv[i])
aa[to] = get(to);
}
int mx = 0, mxi;
for(int i = 1; i <= n; i++){
if(aa[i] > mx)
mx = aa[i], mxi = i;
}
return mxi - 1;
}
