// ~ Be Name Khoda ~ //
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int maxn = 1e6 + 10;
const int maxn5 = (1 << 19) + 10;
const int maxnt = 1.2e6 + 10;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
const int lg = 19;
const ll inf = 1e18;
vector <int> adj[maxn5];
int par[lg][maxn5], l[maxn5], pre[maxn5];
int r[maxn5], id[maxn5], nxt[maxn5];
namespace fen{
int fen[maxn5];
inline void add(int id, int val){
for(++id; id < maxn5; id += id & -id)
fen[id] += val;
}
inline int find(int k){
//cout << "finding " << k << endl;
int id = 0;
for(int i = lg - 1; i >= 0; i--){
//cout << "check for " << i << ' ' << id << ' ' << k << ' ' << fen[id + (1 << i)] << endl;
if(fen[id + (1 << i)] < k){
id += (1 << i);
k -= fen[id];
}
}
//cout << "id of " << id << ' ' << k << endl;
return id;
}
}
void dfs(int v){
//cout << "ok " << v << ' ' << par[0][v] << endl;
for(int i = 1; i < lg && par[i - 1][v] != -1; i++)
par[i][v] = par[i - 1][par[i - 1][v]];
if(adj[v].empty()){
l[v] = r[v] = v;
return;
}
l[v] = mod; r[v] = 0;
for(auto u : adj[v]){
par[0][u] = v;
dfs(u);
l[v] = min(l[v], l[u]);
r[v] = max(r[v], r[u]);
}
}
inline int get_sum(int *k, int l, int r){
return k[r] - (l ? k[l - 1] : 0);
}
int GetBestPosition(int n, int c, int r, int *k, int *s, int *e){
for(int i = 0; i < n; i++){
fen::add(i, 1);
pre[i] = i - 1;
nxt[i] = i + 1;
id[i] = i;
}
int newnode = n;
nxt[n - 1] = -1;
for(int i = 0; i < c; i++){
int st = fen::find(s[i] + 1);
int x = id[st];
int v = pre[x];
int z = newnode++;
id[st] = z;
int tt = e[i] - s[i];
adj[z].pb(x);
while(tt--){
x = nxt[x];
fen::add(x, -1);
adj[z].pb(x);
}
int u = nxt[x];
if(u != -1)
pre[u] = z;
nxt[z] = u;
if(v != -1)
nxt[v] = z;
pre[z] = v;
}
int root = newnode - 1;
memset(par, -1, sizeof par);
for(int i = 0; i < n - 1; i++){
k[i] = (k[i] > r);
if(i)
k[i] += k[i - 1];
}
dfs(root);
int mx = 0, pos = 0;
for(int i = 0; i < n; i++){
int d = 0, v = i;
for(int j = lg - 1; j >= 0; j--)
if(par[j][v] != -1 && get_sum(k, l[par[j][v]], ::r[par[j][v]] - 1) == 0){
v = par[j][v];
d += (1 << j);
}
if(d > mx){
mx = d;
pos = i;
}
}
return pos;
}
