#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()
template<typename T>
int len(T &a){return a.size();}
struct fenwick{
vector<int> t;
int n;
fenwick(){ }
fenwick(int _n){
init(_n);
}
void init(int _n){
n = _n;
t.assign(n,0);
}
void init(vector<int> &a){
init(size(a));
for(int i = 0; i < n; i ++){
inc(i,a[i]);
}
}
void inc(int i, int val = 1){
for(; i < n; i = i | (i + 1)){
t[i] += val;
}
}
int get(int i){
int sum = 0;
for(; i >= 0; i = (i & (i + 1)) - 1){
sum += t[i];
}
return sum;
}
int get(int l, int r){
return get(r) - get(l - 1);
}
int findkthone(int k){
int l = -2, r = n;
while(r - l > 1){
int m = (l + r) / 2;
if(get(m) < k){
l = m;
}else r = m;
}
return r;
}
void out(){
for(int i = 0; i < n; i ++){
cout << get(i) - get(i - 1);
}cout << endl;
}
};
struct DSU{
int n;
vector<int> p, sz;
DSU (){}
DSU (int n) : n(n), p(n), sz(n){
for(int i = 0; i < n; i++){
p[i] = i, sz[i] = 1;
}
}
int get(int a){
return a == p[a] ? a : p[a] = get(p[a]);
}
void unite(int a, int b){
a = get(a), b = get(b);
if(a == b) return;
if(sz[a] < sz[b]) swap(a, b);
sz[a] += sz[b];
p[b] = a;
}
void link(int a, int b){
a = get(a), b = get(b);
if(a == b) return;
p[a] = b;
sz[b] += sz[a];
}
};
template<typename T>
void out(T a){
cout << "{";
for(auto u : a) cout << u << ' ';
cout << "}" << endl;
}
struct Segtree{
int n;
vector<int> t;
int merge(int a, int b){
return max(a, b);
}
Segtree (){}
Segtree (int n) : n(n), t(2 * n){}
void build(vector<int> &a, int _n){
n = _n;
t.resize(2 * n);
for(int i = 0; i < n; i ++){
t[i + n] = a[i];
}
for(int i = n - 1; i > 0; i --){
t[i] = merge(t[i * 2], t[i * 2 + 1]);
}
}
void upd(int i, int val){
i += n;
t[i] = val;
for(i /= 2; i > 0; i /= 2) t[i] = merge(t[i * 2], t[i * 2 + 1]);
}
int get(int l, int r){
l += n; r += n;
int res = 0;
while(l <= r){
if(l & 1){
res = merge(res, t[l ++]);
}
if(!(r & 1)){
res = merge(res, t[r --]);
}
r /= 2;
l /= 2;
}
return res;
}
};
int GetBestPosition(int n, int c, int r, int *k, int *s, int *e){
fenwick f(n);
DSU ds(n + 1);
for(int i = 0; i < n; i ++) f.inc(i, 1);
for(int j = 0; j < c; j ++){
int l = f.findkthone(s[j] + 1);
vector<int> p = {l};
int sz = e[j] - s[j];
s[j] = f.findkthone(s[j]) + 1;
while(len(p) < sz){
l = ds.get(l + 1);
p.push_back(l);
}
e[j] = ds.get(l + 1);
for(auto u : p){
f.inc(u, -1);
ds.link(u, u + 1);
}
}
vector<vector<int>> lef(n);
for(int i = 0; i < c; i ++) lef[s[i]].push_back(e[i]);
int last = 0;
vector<int> pref(n + 1);
for(int i = 0; i < n - 1; i ++){
if(k[i] > r){
if(i == last){
last = i + 1; continue;
}
for(int j = last; j <= i; j ++){
for(auto r : lef[j]){
if(r > i) continue;
pref[j] ++;
pref[r + 1] --;
}
}
last = i + 1;
}
}
if(last != n - 1){
for(int j = last; j < n; j ++){
for(auto r : lef[j]){
if(r > n) continue;
pref[j] ++;
pref[r + 1] --;
}
}
}
int mx = -1;
int ans = 0;
int wins = 0;
for(int i = 0; i < n; i ++){
wins += pref[i];
//cout << wins << endl;
if(mx < wins){
mx = wins;
ans = i;
}
}
return ans;
}
