#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define PB push_back
#define PPB pop_back
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef pair<ll, ll> pll;
const int inf = 1e9 + 7;
const int MAXN = 1e5 + 7;
const int logo = 17;
const int off = 1 << logo;
const int trsz = off << 1;
const int mod = 1e9;
const int dx[] = {0, 0, -1, 1};
const int dy[] = {1, -1, 0, 0};
struct tournament{
int seg[trsz];
void update(int x, int vl){
x += off;
seg[x] = vl;
for(x /= 2; x; x /= 2) seg[x] = seg[x * 2] + seg[x * 2 + 1];
}
int query(int x, int k){
if(x >= off) return (x - off) - 1;
if(seg[x * 2] > k) return query(x * 2, k);
k -= seg[x * 2];
return query(x * 2 + 1, k);
}
}t;
int pf[MAXN], p[MAXN], cnt[MAXN];
vi temp;
set<int> act;
int GetBestPosition(int n, int m, int rank, int *K, int *L, int *R) {
for(int i=0; i<n; i++){
if(i) pf[i] = pf[i - 1];
if(i != n - 1 and K[i] > rank) pf[i]++;
t.update(i, 1);
act.insert(i);
}
for(int i=0; i<m; i++){
int l = t.query(1, L[i]) + 1;
int r = min(t.query(1, R[i] + 1), n - 1);
temp.clear();
auto it = act.lower_bound(l);
while(1){
temp.PB(*it);
it++;
if(it == act.end() or *it > r) break;
}
for(auto &x : temp){
t.update(x, 0);
act.erase(x);
}
t.update(l, 1);
act.insert(l);
//mogu kickat zadnjeg
int vl = pf[r - 1];
if(l != 0) vl -= pf[l - 1];
if(vl == 0){
cnt[l]++;
cnt[r + 1]--;
}
}
ii ans = {-inf, -inf};
for(int i=0; i<n; i++){
if(i) cnt[i] += cnt[i - 1];
//cout << cnt[i] << " " << i << "\n";
ans = max(ans, (ii){cnt[i], -i});
}
return -ans.Y;
}
/*
int kk[MAXN], le[MAXN], ri[MAXN];
void solve(){
int n, m, ja;
cin >> n >> m >> ja;
for(int i=0; i<n-1; i++) cin >> kk[i];
for(int i=0; i<m; i++) cin >> le[i] >> ri[i];
cout << GetBestPosition(n, m, ja, kk, le, ri) << "\n";
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int _ = 1;
//cin >> _;
while(_--) solve();
return 0;
}
*/
