#include <bits/stdc++.h>
using namespace std;
#define rep(i , j , k) for(int i = j; i < (int)k; i++)
constexpr int MAXN = 1e5 + 10;
struct node {
node* par[20];
int l, r;
node(int l_, int r_) {
rep(i , 0 , 20) par[i]= NULL;
l = l_, r = r_;
}
void relax() {
rep(i, 1 , 20)
if (par[i - 1])
par[i] = par[i - 1]->par[i - 1];
}
};
node* a[MAXN];
node* b[MAXN];
node* state[MAXN << 1];
int cnt;
int seg[MAXN << 2];
int le[MAXN], ri[MAXN];
int segGet(int p , int l ,int r, int id = 1) {
if (l == r - 1) return l;
int mid = l + r >> 1;
if (seg[id << 1] >= p) return segGet(p , l , mid ,id << 1);
return segGet(p - seg[id << 1] , mid , r ,id << 1 | 1);
}
void segFlip(int p, int l , int r, int id = 1) {
if (l == r - 1) {
seg[id] ^= 1;
return;
}
int mid = l + r >> 1;
if (p < mid) segFlip(p , l , mid , id << 1);
else segFlip(p , mid , r , id << 1 | 1);
seg[id] = seg[id << 1] + seg[id << 1 | 1];
}
bool smax(int &l, int r) {
if (l < r) {
l = r;
return true;
}
return false;
}
bool smin(int &l, int r) {
if (l > r) {
l = r;
return true;
}
return false;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
rep(i , 0 , N) {
segFlip(i , 0 , N);
state[cnt++] = a[i] = b[i] = new node(i , i);
}
rep(i , 0 , C) {
int s = S[i] + 1;
int sz = E[i] - S[i] + 1;
int last = -1, l = 1e9, r = -1;
node * root = new node(-1 , -1);
rep(z , 0 , sz) {
last = segGet(s , 0 , N);
smin(l , b[last]->l);
smax(r , b[last]->r);
b[last]->par[0] = root;
segFlip(last , 0 , N);
}
segFlip(last , 0 , N);
root->l = l;
root->r = r;
b[last] = root;
state[cnt++] = root;
}
le[0] = -1e9;
rep(i , 1 , N) {
le[i] = le[i - 1];
if (K[i - 1] > R)
le[i] = i - 1;
}
ri[N - 1] = 1e9;
for (int i = N - 2; ~i; i--) {
ri[i] = ri[i + 1];
if (K[i] > R) ri[i] = i + 1;
}
for (int i = cnt - 1; ~i; i--)
state[i]->relax();
int pos = 0, res = -1;
rep(i , 0 , N) {
int local = 0;
node * now = a[i];
for (int j = 19; ~j; j--) {
if (now->par[j] && now->par[j]->l > le[i] && now->par[j]->r < ri[i]) {
local |= 1 << j;
now = now->par[j];
}
}
if (smax(res , local))
pos = i;
}
return pos;
}
