// - Art -
#include <bits/stdc++.h>
#define el cout << '\n'
#define MASK(x) (1 << (x))
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define REV(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define REP(i, c) for (int i = 0, _c = (c); i < _c; ++i)
const int N = 1e5 + 7;
using namespace std;
struct FenwickTree {
int n;
vector<int> bit;
FenwickTree(int _n = 0) : n(_n), bit(_n + 7, 0) {}
void init(int _n) { n = _n; bit.assign(n + 7, 0); }
void update(int u, int add) {
if (u <= 0) return;
for (; u <= n; u += u & -u) bit[u] += add;
}
int get(int u) {
if (u <= 0) return 0;
int res = 0;
for (; u > 0; u -= u & -u) res += bit[u];
return res;
}
int lower_bound(int S) {
if (S <= 1) {
if (n >= 1) return 1;
else return n + 1;
}
int total = get(n);
if (S > total) return n + 1;
int idx = 0;
int bitmask = 1;
while ((bitmask << 1) <= n) bitmask <<= 1;
for (int step = bitmask; step > 0; step >>= 1) {
int nxt = idx + step;
if (nxt <= n && bit[nxt] < S) {
S -= bit[nxt];
idx = nxt;
}
}
return idx + 1;
}
int upper_bound(int S) {
return lower_bound(S + 1);
}
};
int high[N], nxt[N], f[N];
int GetBestPosition(int nPerson, int nRound, int rankTarget, int *rankKnight, int *L, int *R) {
FenwickTree fen(nPerson);
fen.init(nPerson);
for (int i = nPerson - 1; i >= 1; --i) {
rankKnight[i] = rankKnight[i - 1];
}
high[0] = 0;
FOR (i, 1, nPerson) {
if (i <= nPerson - 1) high[i] = high[i - 1] + (rankKnight[i] > rankTarget ? 1 : 0);
else high[i] = high[i - 1];
}
FOR (i, 1, nPerson) {
fen.update(i, +1);
nxt[i] = i + 1;
}
nxt[0] = 1;
FOR(i, 0, nPerson) f[i] = 0;
FOR (i, 1, nRound) {
int Si = L[i - 1];
int Ei = R[i - 1];
++Si; ++Ei;
int Li = fen.lower_bound(Si);
int Ri = fen.upper_bound(Ei);
if (Li > nPerson) Li = nPerson + 1;
if (Ri > nPerson) Ri = nPerson + 1;
int j = nxt[Li];
while (j < Ri) {
fen.update(j, -1);
int tmp = nxt[j];
j = tmp;
}
nxt[Li] = Ri;
if (Ri - 1 >= 1 && Li >= 1 && high[Li] == high[Ri - 1]) {
++f[Li];
--f[Ri];
}
}
FOR (i, 1, nPerson) {
f[i] += f[i - 1];
}
int bestPos1 = 1;
int bestVal = f[1];
FOR (i, 2, nPerson) {
if (f[i] > bestVal) {
bestVal = f[i];
bestPos1 = i;
}
}
return bestPos1 - 1;
}
// int rankKnight[N], L[N], R[N];
// int main() {
// #define name1 "art"
// if (fopen(name1".inp", "r")) {
// freopen(name1".inp", "r", stdin);
// freopen(name1".out", "w", stdout);
// }
// #define name "tournament"
// if (fopen(name".inp", "r")) {
// freopen(name".inp", "r", stdin);
// freopen(name".out", "w", stdout);
// }
// ios_base::sync_with_stdio(false);
// cin.tie(0); cout.tie(0);
// int nPerson, nRound, rankTarget;
// cin >> nPerson >> nRound >> rankTarget;
// REP (i, nPerson - 1) {
// cin >> rankKnight[i];
// }
// REP (i, nRound) {
// cin >> L[i] >> R[i];
// }
// cout << GetBestPosition(nPerson, nRound, rankTarget, rankKnight, L, R) << '\n';
// return 0;
// }
