#include <bits/stdc++.h>
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<
using namespace std;
struct Fenwick {
int n, logn;
vector<int> t;
Fenwick(int n_) : n(n_), logn(32 - __builtin_clz(n)), t(n + 1) {}
void Add(int pos, int val) {
for (++pos; pos <= n; pos += pos & -pos) t[pos] += val;
}
int Find(int val) {
int pos = 0;
for (int i = logn - 1; i >= 0; --i) {
int npos = pos + (1 << i);
if (npos <= n && t[npos] < val) {
pos = npos;
val -= t[npos];
}
}
assert(val == 1);
return pos + 1 - 1;
}
};
int GetBestPosition(int n, int c, int me, int k[], int s[], int e[]) {
Fenwick fw(n);
for (int i = 0; i < n; ++i) {
fw.Add(i, +1);
}
vector<int> nxt(n);
for (int i = 0; i < n; ++i) {
nxt[i] = i + 1;
}
vector<pair<int, int>> interv(c);
for (int i = 0; i < c; ++i) {
int x = s[i], y = e[i];
int l = fw.Find(x + 1);
int pos = l;
for (int step = 0; step < y - x; ++step) {
pos = nxt[pos];
fw.Add(pos, -1);
}
nxt[l] = nxt[pos];
interv[i] = {l, nxt[pos] - 1};
// int r = nxt[pos] - 1;
// dbg() name(l) name(r) endl;
}
vector<int> last_bigger(n + 1, -1);
for (int i = 0; i < n; ++i) {
last_bigger[i + 1] = last_bigger[i];
if (i < n - 1 && k[i] > me) last_bigger[i + 1] = i;
}
vector<int> mars(n + 1);
for (auto &p : interv) {
int l, r; tie(l, r) = p;
// dbg() name(r) name(last_bigger[r]) endl;
if (last_bigger[r] < l) {
++mars[l];
--mars[r];
}
}
pair<int, int> ans = {0, 0};
int cnt = 0;
for (int i = 0; i <= n; ++i) {
cnt += mars[i];
// dbg() name(i) name(cnt) endl;
if (cnt > ans.first) ans = make_pair(cnt, i);
}
return ans.second;
}
