#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
struct node
{
node *l, *r;
int v, res, sz, w, maiorV, maiorRes, lazy;
node(int vv, int rr)
{
v = maiorV = vv, res = maiorRes = rr;
sz = 1, w = rand();
l = r = NULL;
}
};
typedef node*& node_t;
int sz(node *t) {return (t ? t->sz : 0);}
int maiorV(node *t) {return (t ? t->maiorV : -1);}
int maiorRes(node *t) {return (t ? t->maiorRes : -1);}
void op(node *t)
{
if (t)
{
t->sz = sz(t->l)+sz(t->r)+1;
t->maiorV = max({maiorV(t->l), maiorV(t->r), t->v});
t->maiorRes = max({maiorRes(t->l), maiorRes(t->r), t->res});
}
}
void split(node *t, node_t l, node_t r, int pos, int add=0)
{
if (!t) return void(l=r=NULL);
int v = add+sz(t->l);
if (v >= pos) split(t->l, l, t->l, pos, add), r = t;
else split(t->r, t->r, r, pos, v+1), l = t;
op(t);
}
void merge(node_t t, node *l, node *r)
{
if (!l || !r) t = (l ? l : r);
else if (l->w > r->w) merge(l->r, l->r, r), t = l;
else merge(r->l, l, r->l), t = r;
op(t);
}
void insert(node_t t, int pos, int v, int r)
{
node *t1 = NULL, *t2 = NULL;
node *aux = new node(v, r);
split(t, t1, t2, pos);
merge(t1, t1, aux);
merge(t, t1, t2);
op(t);
}
void erase(node_t t, int l, int r)
{
node *t1 = NULL, *t2 = NULL, *t3 = NULL;
split(t, t1, t2, l);
split(t2, t2, t3, r-l+1);
merge(t, t1, t3);
op(t);
}
int query(node *t, int l, int r, bool tipo)
{
node *t1 = NULL, *t2 = NULL, *t3 = NULL;
split(t, t1, t2, l);
split(t2, t2, t3, r-l+1);
int ans = (tipo == 0 ? t2->maiorV : t2->maiorRes);
merge(t2, t2, t3);
merge(t, t1, t2);
return ans;
}
int findV(node *t, int l, int r, int v, int add=0)
{
int ind = add+sz(t->l);
if (ind < l) return findV(t->r, l, r, v, ind+1);
if (ind > r) return findV(t->l, l, r, v, add);
if (t->v == v) return t->res;
else if (maiorV(t->l) == v && add+sz(t->l->l) >= l) return findV(t->l, l, r, v, add);
return findV(t->r, l, r, v, add);
}
int findRes(node *t, int l, int r, int res, int add=0)
{
int ind = add+sz(t->l);
if (ind < l) return findRes(t->r, l, r, res, ind+1);
if (ind > r) return findRes(t->l, l, r, res, add);
if (t->res == res) return t->v;
else if (maiorRes(t->l) == res && add+sz(t->l->l) >= l) return findRes(t->l, l, r, res, add);
return findRes(t->r, l, r, res, add);
}
int back[maxn];
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E)
{
node *t = NULL;
for (int i = 0; i < N-1; i++)
{
insert(t, i, K[i], 0);
back[K[i]] = i;
}
insert(t, N-1, N, 0);
back[N] = N-1;
int ans = 0, pos = 0;
for (int i = 0; i < C; i++)
{
int l = S[i], r = E[i];
int mx = query(t, l, r-1, 0);
int mr = query(t, l, r, 1);
if (mr > ans)
{
ans = mr;
pos = back[findRes(t, l, r, mr)];
}
if (mx > R)
{
int ant = findV(t, l, r-1, mx);
erase(t, l, r);
insert(t, l, mx, ant);
}
else
{
int ant = findRes(t, l, r, mr);
erase(t, l, r);
insert(t, l, ant, mr+1);
}
}
int mr = query(t, 0, t->sz-1, 1);
if (mr > ans) pos = back[findRes(t, 0, t->sz-1, mr)];
return pos;
}
