#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define pb push_back
#define s second
#define f first
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
const int MxN=1e5+10, INF=1e9;
int n, Rank, Start[MxN], s[MxN], e[MxN], fen[MxN], t[4*MxN], mx[MxN];
vi ad[MxN];
void upd(int p, int x)
{
for(int i=p; i<MxN; i+=i&(-i)) fen[i]+=x;
}
int get(int p)
{
int ret=0;
for(int i=p; i>0; i-=i&(-i)) ret+=fen[i];
return ret;
}
int get_lin(int x)
{
int l=1, r=n;
while(l<r){
int m=(l+r)/2;
if(get(m)<x) l=m+1;
else r=m;
}
return l;
}
int get_rin(int x)
{
int l=1, r=n;
while(l<r){
int m=(l+r+1)/2;
if(get(m)>x) r=m-1;
else l=m;
}
return l;
}
void upd_max(int p, int x, int l=1, int r=n, int id=1)
{
if(l==r){
t[id]=x;
return;
}
int m=(l+r)/2;
if(p<=m) upd_max(p, x, l, m, id*2);
else upd_max(p, x, m+1, r, id*2+1);
t[id]=max(t[id*2], t[id*2+1]);
}
int get_max(int x, int y, int l=1, int r=n, int id=1)
{
if(r<x||l>y) return -1;
if(x<=l&&r<=y) return t[id];
int m=(l+r)/2;
return max(
get_max(x, y, l, m, id*2),
get_max(x, y, m+1, r, id*2+1)
);
}
int ans, max_wins;
void dfs(int u, int wins=0)
{
// cout << u << " " << wins << endl;
if(int(ad[u].size())==0 && mx[u]==Rank){
wins++;
if(wins>max_wins){
max_wins=wins;
ans=Start[u];
}
}
for(auto it : ad[u]){
if(mx[u]==Rank) dfs(it, wins+1);
else dfs(it, 0);
}
}
int GetBestPosition(int N, int c, int r, int *k, int *S, int *E) {
n=N; Rank=r; FOR(i, 0, c) s[i]=S[i], e[i]=E[i];
set<pii> st;
FOR(i, 1, n+1) upd(i, 1), st.insert({i,-1});
FOR(i, 1, n)
{
upd_max(i, k[i-1]);
}
FOR(i, 0, c)
{
int l_in=get_lin(s[i]+1), r_in=get_rin(e[i]+1);
mx[i]=max(get_max(l_in, r_in-1), r);
// cout << i << ": " << l_in << " " << r_in << " -> " << mx[i] << '\n';
vector<pii> er;
auto it=st.lower_bound({l_in,-1});
while(it!=st.end() && (*it).f<=r_in){
er.pb(*it);
int pos=(*it).f, in=(*it).s;
if(in!=-1) ad[i].pb(in);
upd(pos, -1);
it++;
}
for(auto iter : er) st.erase(iter);
st.insert({l_in,i});
Start[i]=l_in-1;
upd(l_in, 1);
// cout << i << ": ";
// for(auto iter : ad[i]) cout << iter << " ";
// cout << '\n';
}
dfs(c-1);
// cout << "wins: " << max_wins << endl;
return ans;
}
