#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
const int LOGN = 20;
struct Binary_Lifting{
int pai[2*N][LOGN];
int maxval;
void build(){
maxval = 1;
for(int i = 0;i < 2*N;i++){
pai[i][0] = i;
}
}
void add(int a, int b){
pai[a][0] = b;
maxval = max(maxval, b);
}
void construct(){
for(int bit = 1;bit < LOGN;bit++){
for(int i = 1;i <= maxval;i++){
pai[i][bit] = pai[pai[i][bit-1]][bit-1];
}
}
}
int query(int pos, int qtd){
for(int i = 0;i < LOGN;i++){
if(((1<<i)&qtd)){
pos = pai[pos][i];
}
}
return pos;
}
} bin;
struct Segtree{
int tree[4*N], lazy[4*N];
void build(int node, int l, int r){
lazy[node] = -1;
if(l == r){
tree[node] = 1;
return;
}
int mid = (l+r)/2;
build(2*node, l, mid);
build(2*node+1, mid+1, r);
tree[node] = tree[2*node]+tree[2*node+1];
return;
}
void unlazy(int node, int l, int r){
if(lazy[node] == -1) return;
tree[node] = lazy[node]*(r-l+1);
if(l != r){
lazy[2*node] = lazy[node];
lazy[2*node+1] = lazy[node];
}
lazy[node] = -1;
}
void update(int node, int l, int r, int tl, int tr, int val){
unlazy(node, tl, tr);
if(l > tr or tl > r) return;
if(l <= tl and tr <= r){
lazy[node] = val;
unlazy(node, tl, tr);
return;
}
int mid = (tl+tr)/2;
update(2*node, l, r, tl, mid, val);
update(2*node+1, l, r, mid+1, tr, val);
tree[node] = tree[2*node]+tree[2*node+1];
return;
}
int query(int node, int l, int r, int tl, int tr){
unlazy(node, tl, tr);
if(l > tr or tl > r) return 0;
if(l <= tl and tr <= r) return tree[node];
int mid = (tl+tr)/2;
return query(2*node, l, r, tl, mid)+query(2*node+1, l, r, mid+1, tr);
}
int search(int node, int l, int r, int val){
if(l == r) return l;
int mid = (l+r)/2;
if(tree[2*node] >= val) return search(2*node, l, mid, val);
else return search(2*node+1, mid+1, r, val-tree[2*node]);
}
} seg;
struct DSU{
int pai[N], val[N];
void build(){
for(int i = 0;i < N;i++){
pai[i] = i;
val[i] = i;
}
}
pair <int, int> find(int x){
if(x == pai[x]) return {x, val[x]};
auto [p, v] = find(pai[x]);
pai[x] = p;
val[x] = v;
return {p, v};
}
void join(int a, int b, int v){
a = find(a).first;
b = find(b).first;
if(a == b) {
val[a] = v;
return;
}
if(a > b) swap(a, b);
pai[a] = b;
val[b] = v;
}
void query(int l, int r, int valor){
vector <pair <int, int>> juntar;
while(l <= r){
auto [rr, v] = find(l);
l = rr+1;
juntar.push_back({rr, v});
}
for(auto [x, v] : juntar){
join(x, r, valor);
bin.add(v, valor);
}
}
} dsu;
vector <array <int, 3>> intervalos;
pair <int, int> inter[2*N];
int GetBestPosition(int n, int c, int r, int *k, int *s, int *e) {
seg.build(1, 1, n);
for(int i = 0;i < c;i++){
int l = (s[i] == 0 ? 1 : seg.search(1, 1, n, s[i])+1);
int r = seg.search(1, 1, n, e[i]+1);
intervalos.push_back({l, r, i+1+n});
seg.update(1,l, r-1, 1, n, 0);
}
dsu.build();
bin.build();
for(auto [l, r, v] : intervalos){
dsu.query(l, r, v);
inter[v] = {l, r};
}
for(int i = 1;i <= n;i++){
inter[i] = {i, i};
}
/*for(int i = 1;i <= bin.maxval;i++){
cout << inter[i].first << ' ' << inter[i].second << endl;
}*/
bin.construct();
seg.update(1, 1, 1, 1, n, 0);
for(int i = 2;i <= n;i++){
int valor = k[i-2];
if(k[i-2] < r) seg.update(1, i, i, 1, n, 0);
else seg.update(1, i, i, 1, n, 1);
}
int res = 0, qtd = -1;
for(int i = 1;i <= n;i++){
int l = 0, r = bin.maxval;
int ans = 0;
while(l <= r){
int mid = (l+r)/2;
int valor = bin.query(i, mid);
int valor2 = bin.query(i, mid-1);
if(valor == valor2) r = mid-1;
else{
int v = seg.query(1, inter[valor].first, inter[valor].second, 1, n);
if(i == 4 and mid == 1){
//cout << valor << ' ' << inter[valor].first << ' ' << inter[valor].second << endl;
}
if(v == 0){
ans = mid;
l = mid+1;
}
else{
r = mid-1;
}
}
}
//cout << ans << ' ';
if(ans > qtd){
res = i-1;
qtd = ans;
}
if(i == n) break;
int t = seg.query(1, i+1, i+1, 1, n);
seg.update(1, i, i, 1, n, t);
seg.update(1, i+1,i+1, 1, n, 0);
}
return res;
}
