//In the name of God
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const ll maxn = 3e5 + 100;
const ll mod = 1e9 + 7;
const ll inf = 1e18;
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()
#define lc (id << 1)
#define rc (lc | 1)
ll seg[maxn << 2];
void bld(ll id, ll s, ll e){
seg[id] = e - s;
if(e - s == 1) return;
ll mid = (s + e) >> 1;
bld(lc, s, mid);
bld(rc, mid, e);
return;
}
void upd(ll id, ll s, ll e, ll l, ll r){
if(seg[id] == 0 || r <= s || e <= l) return;
if(l <= s && e <= r){
seg[id] = 0;
return;
}
ll mid = (s + e) >> 1;
upd(lc, s, mid, l, r);
upd(rc, mid, e, l, r);
seg[id] = seg[lc] + seg[rc];
return;
}
ll get(ll id, ll s, ll e, ll x){
if(seg[id] < x) return e;
if(e - s == 1) return s;
ll mid = (s + e) >> 1;
if(seg[lc] < x) return get(rc, mid, e, x - seg[lc]);
return get(lc, s, mid, x);
}
ll dp[maxn], ok[maxn], l[maxn], r[maxn], b[maxn];
vector<ll> g[maxn];
void dfs(ll v){
dp[v] += ok[v];
for(ll u : g[v]){
dp[u] += dp[v];
dfs(u);
}
return;
}
int GetBestPosition(int n, int c, int x, int *a, int *s, int *e){
bld(1, 0, n);
set<ll> st, ss;
for(ll i = 0; i < n; i++){
st.insert(i);
b[i] = i;
}
for(ll i = 0; i < n - 1; i++){
if(a[i] > x) ss.insert(i);
}
ss.insert(n);
for(ll i = 0; i < c; i++){
l[n + i] = get(1, 0, n, s[i] + 1);
r[n + i] = get(1, 0, n, e[i] + 2);
upd(1, 0, n, l[n + i] + 1, r[n + i]);
auto it = st.lower_bound(l[n + i]);
while(it != st.end() && *it < r[n + i]){
g[n + i].pb(b[*it]);
it = st.erase(it);
}
b[l[n + i]] = n + i;
st.insert(l[n + i]);
if(*ss.lower_bound(l[n + i]) >= r[n + i] - 1) ok[n + i] = 1;
}
dfs(n + c - 1);
ll ans = 0;
for(ll i = 0; i < n; i++){
if(dp[i] > dp[ans]) ans = i;
}
return ans;
}
/*int main(){
fast_io;
int n, c, x, a[100], s[100], e[100];
cin >> n >> c >> x;
for(ll i = 0; i < n - 1; i++){
cin >> a[i];
}
for(ll i = 0; i < c; i++){
cin >> s[i] >> e[i];
}
cout << GetBestPosition(n, c, x, a, s, e);
return 0;
}*/
