#include <bits/stdc++.h>
using namespace std;
/*
filas
pos L é ultima com L atrás dela
pos R também
*/
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pdd;
const int MAXN = 1e5+10;
void updt(vector<int> &bit, int p, int v){
p++;
while (p<bit.size()){
bit[p]+=v;
p += p&-p;
}
}
int qry(vector<int> &bit, int p){
p++;
int ss = 0;
while (p>0){
ss += bit[p];
p -= p&-p;
}
return ss;
}
int nrmr(int l, vector<int> &bit, int n){
int in = 0, fi = n-1, me;
// ultima com até l atras
while (in<=fi){ // da pra deixar log ao invés de log²
me = (in+fi)/2;
int at = qry(bit, me-1);
if (at<=l) in=me+1;
else fi = me-1;
}
return in-1;
}
int nrml(int l, vector<int> &bit, int n){
int in = 0, fi = n-1, me;
// primeira com ao menos l atras
while (in<=fi){ // da pra deixar log ao invés de log²
me = (in+fi)/2;
int at = qry(bit, me-1);
if (at>=l) fi = me-1;
else in = me+1;
}
return fi+1;
}
int lm;
void bseg(vector<int> &seg, int id, int il, int ir, int *K){
if (il==ir){
if (il==lm) seg[id]=-1;
else seg[id] = K[il-1];
return;
}
int m = (il+ir)/2;
bseg(seg, 2*id, il, m, K);
bseg(seg, 2*id+1, m+1, ir, K);
seg[id] = max(seg[2*id], seg[2*id+1]);
}
int qseg(vector<int> &seg, int id, int il, int ir, int l, int r){
if (ir<l || il>r) return -1;
if (il>=l && ir<=r) return seg[id];
int m = (il+ir)/2;
return max(qseg(seg, 2*id, il,m,l,r), qseg(seg, 2*id+1, m+1, ir, l, r));
}
int GetBestPosition(int n, int c, int r, int *K, int *L, int *R){
lm=n;
// ajustar jousts
vector<int> bit(n, 0);
set<int> pr;
for (int i=0;i<n-1;i++){
updt(bit, i, 1);
pr.insert(i);
}
vector<vector<int>> q(n+1);
for (int i=0;i<c;i++){
L[i] = nrml(L[i], bit, n), R[i] = nrmr(R[i], bit, n);
// remover todo mundo menos o cara da direita
auto it = pr.lower_bound(L[i]);
while (it != pr.end() && *it < R[i]){
updt(bit, *it, -1);
pr.erase(it);
it = pr.lower_bound(L[i]);
}
q[L[i]].push_back(R[i]);
}
vector<int> seg(4*(n+1), -1);
bseg(seg, 1, 1, n, K);
vector<pii> inc; // l menores tem sempre r maiores (logo, mais à esquerda em inc veio antes)
int pos=0, ans=-1;
for (int i=0;i<=n-1;i++){ // botando atras de i (em i) (se alguem acaba em i ninguem começa em i)
while (!q[i].empty()){
inc.emplace_back(i, q[i].back()-1);
q[i].pop_back();
}
int v = 0;
int in = 0, fi = inc.size()-1, me;
while (in<=fi){
me = (in+fi)/2;
int x = qseg(seg, 1, 1, n, inc[me].first+1, inc[me].second+1); // maior no intervalo
if (x<r) fi = me-1, v = inc.size()-me;
else in = me+1;
}
if (v>ans){
ans=v, pos=i;
}
while (!inc.empty() && inc.back().second<i) inc.pop_back();
}
return pos;
}
// int K[MAXN], L[MAXN], R[MAXN];
// signed main(){ // DEBUG ONLY
// std::ios_base::sync_with_stdio(false);
// cin.tie(nullptr);
// int n, c, r;
// cin >> n >> c >> r;
// for (int i=0;i<n-1;i++) cin >> K[i];
// for (int i=0;i<c;i++){
// cin >> L[i] >> R[i];
// }
// cout << GetBestPosition(n, c, r, K, L, R) << '\n';
// return 0;
// }
